This slide was wrote for in-house presentation which named FFLT
What is PFDS
Purely Functional Data Structure
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