Purely Functional Data Structures

Author: Chris Okasaki
All Stack Overflow 46
This Year Stack Overflow 1
This Month Stack Overflow 1


by anonymous   2019-01-13

By functional I assume you mean an immutable queue?

If you use F# and .NET there are for example:

If you like to read on how to implement a functional queue I recommend Purely Functional Data Structures by Chris Okasaki.

One of the first ways Okasaki implements a functional queue is using two List<>, one you pop from and one you push to. When the pop list is empty the push queue is reversed and becomes the pop list.

Bear in mind this is in many ways a rather inefficient queue but it's also rather simple:

type Queue<'T> = 'T list*'T list

let empty<'T> : Queue<'T> = [], []

let isEmpty ((f, r) : Queue<'T>) : bool =
  match f, r with
  | []    , []  -> true
  | _     , _   -> false

let headAndTail ((f, r) : Queue<'T>) : 'T*Queue<'T> =
  match f, r with
  | []    , []  -> failwith "Queue is empty"
  | v::vs , r   -> v, (vs, r)
  | _     , r   -> let v::vs = List.rev r in v, (vs, [])

let snoc ((f, r) : Queue<'T>) (v : 'T) : Queue<'T> = (f, v::r)

let fold (f : 'S -> 'T -> 'S) (s : 'S) (q : Queue<'T>) : 'S =
  let rec loop ss qq =
    if isEmpty qq then ss
      let hh, tt = headAndTail qq
      loop (f ss hh) tt
  loop s q

let ofArray (vs : 'T []) : Queue<'T> = vs |> Array.fold snoc empty

let main argv = 
  let q = [| 1..20 |] |> ofArray
  fold (fun _ v -> printfn "%A" v) () q
by bcherny   2019-01-10
+1 Okasaki’s book is a great reference. I’ve personally given out a few as gifts.


by davidcuddeback   2017-12-12
> A data structure cannot be functional.

I think the author is using the term "purely functional data structure" to mean a data structure that lends itself to an implementation in a purely functional language [1,2].

[1] https://www.amazon.com/Purely-Functional-Structures-Chris-Ok...

by axiomabsolute   2017-08-20
The canonical text discussing how this is achieved refers to data structures optimized for immutability as "purely functional data structures". [1] These type of data structures are the default for Clojure as well, and there are a number of blog posts and presentations discussing their implementation. [2] [3]

It's a reasonably complicated topic, but the basic idea is that since the data structures are immutable, much of their structure can be shared between versions with few changes. Most of these data structures end up using a Tree of some sort. Performance characteristics can be influenced to an extent by using bucketing to control the width/height of the tree.

[1] : Purely Functional Data Structures (Amazon: https://www.amazon.com/Purely-Functional-Structures-Chris-Ok...) [2] http://hypirion.com/musings/understanding-persistent-vector-... [3] https://www.youtube.com/watch?v=7BFF50BHPPo

by anonymous   2017-08-20

This article, Haskell: Queues without pointers, describes a purely functional queue with O(1) amortized cost (edit: for adding and removing elements). I think the data structure comes from Chris Okasaki and more details are in his book.

The basic idea is to decompose the queue into two lists, one for the front and one for the back. New elements are added to "front". "Back" is stored in reverse order, to facilitate popping elements. When all elements of "back" are gone, "front" is reversed and re-identified as "back". This data structure has O(1) amortized cost for these operations, but apparently with some work it can be reduced to O(1), proper.

Edit: Okasaki's paper describes an elegant, purely functional implementation of queues and double-ended queues (deques). Deques allow adding or removing elements from either end. All such operations are O(1), worst case.

by anonymous   2017-08-20

First of all, don't do premature optimisations. Have you measured your code? Maybe there is some concrete bottlenecks?

Since most of the objects consist of smaller objects joined via data stuctures, I think you can get rid of this problem by using persistent data structures .

persistent data structure is a data structure which always preserves the previous version of itself when it is modified; such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure

Here is wonderful talk about some of them by Daniel Spiewak. If you want more, take a look on Purely Functional Data Structures by Chris Okasaki.

by anonymous   2017-08-20

You can use a purely functional map implementation, where you just ignore the values.

See http://hackage.haskell.org/packages/archive/containers/ (linked to from https://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki ).

(sidenote: For more information on functional datastructures, see http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504 )

by anonymous   2017-08-20

I don't think there's a shortcut here.

Just as you imply, Clojure's persistent data structures are quite a different thing from the immutable collections classes that Cocoa provides.

If you want to use Clojure's persistent data structures from Obj-C, the only way to do so is to re-implement them in Objective-C. My understand is that many of these are described in Okasaki's book, Purely Functional Data Structures, and in the papers of Phil Bagwell.

This other answer has some links: What is the data structure behind Clojure's sets?.

by anonymous   2017-08-20

A related question was asked before: "Does functional programming replace GoF design patterns", with great responses.

The equivalent of "design patterns" is very vague in FP. In general, every time you see a "pattern" in your code you should create something to cover all of its uses in a uniform way. Often it will be a higher-order function.

For example, the following C code

for (int i = 0; i < n; i++)
  if (a[i] == 42)
    return true;
return false;

can be thought of some basic "design pattern" - checking if there's some special element on the list. This snippet could appear many times in code with different conditions. In FP, you simply use a higher order function several times. It's not a "pattern" anymore.

Functional programming has its own practices, but they are much different from "design patterns" in OOP. They include use of polymorphism, lists, higher-order functions, immutability/purity, laziness [not all are essential or specific to FP]... See also "what are core concepts of FP". Also, type classes (Haskell), modules and functors (OCaml), continuations, monads, zippers, finger trees, monoids, arrows, applicative functors, monad transformers, many purely functional data structures (book) etc. Functional pearls, already mentioned by Randall Schulz, form a very rich resource of FP at its best.

To learn how to write idiomatic code, any book/resource on a functional programming language will suffice IMHO (for example, RWH and LYAH); differences between thinking imperatively and functionally are always explained there.

In dynamic languages, Jeff Foster's link is a good collection; here is a very clever use of memoization in JavaScript that could be considered a "design pattern".

by anonymous   2017-08-20

You could try references to his book by Haskell or Clojure folk rather than just the CMU pdf : e.g.,


There was a question here on SO at :

What is the benefit of purely functional data structure?

There is also Clojure area this :


And there was this on SE :


Hope something there provides a basis for a search that bears results :-)

You may have to use an academic or biz ref search engine and you may want to look at poster sessions at a conf because search is not obvious here, e.g., Mercury can generate Erlang code ... so searching caching and locality with respect to performance in functional programming in some hardware area dealing with latency.

Canada'a National Research Council (NRC) had some work going on ... you could try a search of their pub's/notices/reports

But note: a search with

bigdata latency locality NRC 2012

gives rather different result from

bigdata functional latency locality NSF 2012

( and I would next drop the 2012 and try using the google search tool date range option for recent results)