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)).