data-structures - 来自第一个元素列表数据结构的功能 O(1) 追加和 O(n) 迭代

Question

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

追加，O(1)

在顺序迭代中，O(n)

一个普通的函数链表只支持 O(n) 追加，而我可以使用一个普通的 LL 然后反转它，反向操作也是 O(n)，它(部分)否定 O(1) cons 操作。

Answer 1

您可以使用 John Hughes 的恒定时间附加列表，现在似乎将其称为 DList .表示是一个从列表到列表的函数:空列表是恒等函数； append 是组合，singleton 是 cons(部分应用)。在这种表示中，每次枚举都将花费您 n分配，所以可能不是那么好。

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

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

枚举是一种树形遍历，它要么会消耗一些堆栈空间，要么需要某种 zipper 表示。这是转换为列表但使用堆栈空间的树遍历:

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

您可以编写一个 fold 函数来访问相同的元素，但实际上并不具体化列表；只需用更一般的东西替换 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

那是您的线性时间、常量堆栈枚举。玩得开心!