功能O(1)从第一个元素列表数据结构追加和O(n)迭代

Question

我正在寻找支持以下操作的功能数据结构:

• 附加,O(1)
• 按顺序迭代,O(n)

正常的功能链表仅支持O(n)附加,而我可以使用普通LL然后反转它,反向操作也是O(n),它(部分地)否定O(1)cons操作.

Answer 1

您可以使用John Hughes的常量追加列表,这些列表现在看起来很有用DList.表示是从列表到列表的函数:空列表是标识函数; 追加是组合,单身是缺点(部分应用).在此表示中,每个枚举都会花费您的n分配,因此可能不太好.

另一种方法是将相同的代数作为数据结构:

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

枚举是一个树遍历,它将花费一些堆栈空间或需要某种拉链表示.这是一个转换为列表但使用堆栈空间的树遍历:

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 []

这是相同的,但使用不断的堆栈空间:

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 []

您可以编写一个折叠函数来访问相同的元素,但实际上并没有重新列出该列表; 只需用更通用的东西替换cons和nil:

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

这是你的线性时间,常量堆栈枚举.玩得开心!

Answer 2

我相信你可以使用标准的功能链表:

• 要追加元素,可以使用cons(即O(1))
• 要按插入顺序迭代元素,您可以先反转列表
  (即O(N))然后遍历它,也就是O(N)(并且2xO(N)仍然只是O( N)).

Answer 3

差异清单怎么样？

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 []