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!

Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account log in.