LoginSignup
0

More than 5 years have passed since last update.

What should we know about PFDS

Posted at
1 / 9

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!

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0