# What should we know about PFDS

More than 1 year has passed since last update.

This slide was wrote for in-house presentation which named `FFLT`

# Purely Functional Data Structure?

• Data structure without destructive assignment
• Achieve the same efficiency as well as imperative data structure
• Computational complexity with lazy evaluation
• Sample codes are written by Standard ML and (almost) Haskell

# Sample code (LinkedList)

We assume interface like this

```type t =
| Null
| Cons of { element: int; tail: t; }

val empty: t

(* cons 1 [2] -> [1, 2] *)
val cons: int -> t -> t

(* concat [1, 2] [3, 4] -> [1, 2, 3, 4] *)
val concat: t -> t -> t
```

# Imperative way O(1)

```// JavaScript
const empty = null;
const cons = element => next => ({ element, next, _tail: next === empty ? empty : next.next })
const concat = xs => ys => {
if (xs === empty) return ys
xs._tail.next = ys
xs._tail = ys._tail
return xs
}

const list_a = cons(1)(cons(2)(cons(3)(empty)))
const list_b = cons(4)(cons(5)(cons(6)(empty)))

console.log(list_a); // [1, 2, 3]
console.log(list_b); // [4, 5, 6]

console.log(require("util").inspect(
concat(list_a)(list_b),  // [1, 2, 3, 4, 5, 6]
{ showHidden: true, depth: null }
));

console.log(list_a); // A careful audience might take notice that we already can't use the first list normally because `concat` function destroyed its held reference
```

# Functional way O(n)

```// JavaScript
const empty = null;
const cons = element => next => ({ element, next })
const concat = xs => ys => (xs === empty) ?
ys :
cons(xs.element)(concat(xs.next)(ys))

const list_a = cons(1)(cons(2)(cons(3)(empty)))
const list_b = cons(4)(cons(5)(cons(6)(empty)))

console.log(list_a); // [1, 2, 3]
console.log(list_b); // [4, 5, 6]

console.log(require("util").inspect(
concat(list_a)(list_b),  // [1, 2, 3, 4, 5, 6]
{ showHidden: true, depth: null }
));

console.log(list_a);
console.log(list_b);
// We can use both list normally, On the other words we can use it persistently
```