What should we know about PFDS

  • 2
    Like
  • 0
    Comment

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

We can start immediately, Now!