Functional O(1) append and O(n) iteration from first element list data structure

Question

I'm looking for a functional data structure that supports the following operations:

• Append, O(1)
• In order iteration, O(n)

A normal functional linked list only supports O(n) append, while I could use a normal LL and then reverse it, the reverse operation would be O(n) also which (partially) negates the O(1) cons operation.

Answer 1

You can use John Hughes's constant-time append lists, which seem nowadays to be called DList. The representation is a function from lists to lists: the empty list is the identity function; append is composition, and singleton is cons (partially applied). In this representation every enumeration will cost you n allocations, so that may not be so good.

The alternative is to make the same algebra as a data structure:

type 'a seq = Empty | Single of 'a | Append of 'a seq * 'a seq

Enumeration is a tree walk, which will either cost some stack space or will require some kind of zipper representation. Here's a tree walk that converts to list but uses stack space:

let to_list t =
  let rec walk t xs = match t with
  | Empty -> xs
  | Single x -> x :: xs
  | Append (t1, t2) -> walk t1 (walk t2 xs) in
  walk t []

Here's the same, but using constant stack space:

let to_list' t =
  let rec walk lefts t xs = match t with
  | Empty -> finish lefts xs
  | Single x -> finish lefts (x :: xs)
  | Append (t1, t2) -> walk (t1 :: lefts) t2 xs
  and finish lefts xs = match lefts with
  | [] -> xs
  | t::ts -> walk ts t xs in
  walk [] t []

You can write a fold function that visits the same elements but doesn't actually reify the list; just replace cons and nil with something more general:

val fold : ('a * 'b -> 'b) -> 'b -> 'a seq -> 'b

let fold f z t =
  let rec walk lefts t xs = match t with
  | Empty -> finish lefts xs
  | Single x -> finish lefts (f (x, xs))
  | Append (t1, t2) -> walk (t1 :: lefts) t2 xs
  and finish lefts xs = match lefts with
  | [] -> xs
  | t::ts -> walk ts t xs in
  walk [] t z

That's your linear-time, constant-stack enumeration. Have fun!

Answer 2

I believe you can just use standard functional linked list:

• To append element, you can use cons (which is O(1))
• To iterate elements in the order in which they were inserted, you can first reverse the list,
  (which is O(N)) and then traverse it, which is also O(N) (and 2xO(N) is still just O(N)).

Answer 3

How about a difference list?

type 'a DList = DList of ('a list -> 'a list)

module DList =
  let append (DList f) (DList g) = (DList (f << g))
  let cons x (DList f) = (DList (fun l -> x::(f l)))
  let snoc (DList f) x = (DList (fun l -> f(x::l)))
  let empty = DList id
  let ofList = List.fold snoc empty
  let toList (DList f) = f []

Answer 4

What about a circularly-linked list? It supports O(1) appends and O(n) iteration.

Answer 5

You could create a functional Deque, which provides O(1) adding to either end, and O(N) for iteration in either direction. Eric Lippert wrote about an interesting version of an immutable Deque on his blog note that if you look around you will find the other parts of the series, but that is the explanation of the final product. Note also that with a bit of tweaking it can be modified to utilize F# discriminated unions and pattern matching (although that is up to you).

Another interesting property of this version, O(1) peek, removal, and add, from either end (i.e. dequeueLeft, dequeueRight, dequeueLeft, dequeueRight, etc. is still O(N), versus O(N*N) with a double list method).