从第一个元素列表数据结构进行功能 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 []

Answer 4

您可以创建一个函数式双端队列，它提供 O(1) 添加到任一端，以及 O(N) 进行任一方向的迭代。 Eric Lippert 写了一篇关于不可变双端队列的有趣版本 在他的博客上请注意，如果您环顾四周，您会发现该系列的其他部分，但这是对最终产品的解释。另请注意，通过一些调整，可以将其修改为利用 F# 可区分联合和模式匹配（尽管这取决于您）。

此版本的另一个有趣的属性，O(1) 从任一端查看、删除和添加（即 dequeueLeft、dequeueRight、dequeueLeft、dequeueRight 等，仍然是 O(N)，而 O( N*N），采用双列表方法）。

Answer 5

循环链表怎么样？它支持 O(1) 追加和 O(n) 迭代。