功能O（1）从第一个元素列表数据结构追加和O（n）迭代 [英] Functional O(1) append and O(n) iteration from first element list data structure

问题描述

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

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

• 追加，O（1）


• 按顺序迭代，O（n）

正常的功能链表只支持O（n） ，而我可以使用一个正常的LL，然后反转它，反向操作将是O（n），也是（部分地）否定O（1）cons操作。

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.

推荐答案

您可以使用John Hughes的常规追加列表，这些列表现在似乎被称为 DList 。表示是从列表到列表的函数：空列表是身份函数;附加是组合，单身是cons（部分应用）。在这个表示法中，每个枚举会花费你 n 分配，所以可能不是那么好。

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!

这篇关于功能O（1）从第一个元素列表数据结构追加和O（n）迭代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！