差异列表的显式纯函数数据结构 [英] Explicit Purely-Functional Data-Structure For Difference Lists

问题描述

在 Haskell 中，差异列表，从某种意义上说

In Haskell, difference lists, in the sense of

[a] 具有高效连接操作的列表表示

[a] representation of a list with an efficient concatenation operation

似乎是在功能上实现的组成.

函数和(动态)函数组合，虽然，也必须使用数据结构以某种方式在计算机的内存中表示，这提出了如何dlists 可以在 Haskell 中实现， 不使用函数组合，而是通过一些基本的纯功能节点数据结构.如何在与函数组合相同的性能保证下做到这一点?

Functions and (dynamic) function compositions, though, must also be represented somehow in the computer's memory using data structures, which raises the question of how dlists could be implemented in Haskell without using function compositions, but, rather, through some basic purely-functional node-based data structures. How could this be done with the same performance guarantees as those of function composition?

推荐答案

如这个答案 诀窍是在访问时将 (.) 树重新排列到 ($) 列表中.

As shown in this answer the trick is the rearrangement of (.) tree into the ($) list on access.

我们可以模仿这个

data Dlist a = List [a]  
             | Append (Dlist a) (Dlist a)

将处理 Append 节点，将树向右旋转，将最左边的节点向上推，使其在第一次访问时成为最左上角，然后下一个 tail^(**) 操作变成O(1) ^(*) :

which will juggle the Append nodes, rotating the tree to the right, to push the leftmost node up so it becomes the uppermost-left, on the first access, after which the next tail^(**) operation becomes O(1) ^(*) :

let x = (List [1..10] `Append` List [11..20]) `Append` List [21..30]

和tail x^(**)就是产生

List [2..10] `Append` (List [11..20] `Append` List [21..30])

tail^(**) 应该很容易实现.当然 if 只会匹配最左边的 List 节点的列表(使用 (x:xs))当该节点最终被发现时，并且不会触及任何其他内容在 Append 节点内，因为它们是杂耍的.懒惰因此自然而然地得以保留.

tail^(**) should be trivial to implement. Of course if will only pattern match the leftmost List node's list (with (x:xs)) when that node is finally discovered, and won't touch contents of anything else inside the Append nodes as they are juggled. Laziness is thus naturally preserved.

^(**) 2020 编辑:这实际上意味着有一个 uncons :: Dlist a ->(a, Dlist a) 操作同时产生头部和新的、旋转的尾部，因此 new 尾部的 uncons 是 O(1).^(*)

^(**) 2020 edit: what this actually means is to have one uncons :: Dlist a -> (a, Dlist a) operation producing the head and the new, rotated tail, simultaneously, so that uncons on the new tail is O(1).^(*)

^(*) edit: O(1) 如果最左边的 List 节点的列表不是空的.总的来说，考虑到可能嵌套在左侧的 Append 节点必须重新排列，因为 它们 在第一个最左边的 List 之后出现节点耗尽，访问结果的所有n个元素将是O(n+m)，其中m是空列表的数量.

^(*) edit: O(1) in case the leftmost List node's list isn't empty. Overall, taking into account the possible nested-on-the-left Append nodes that will have to be rearranged as they come to the fore after the first leftmost List node is exhausted, the access to all n elements of the result will be O(n+m), where m is the number of empty lists.

更新: 历史注释:这实际上与有效树边缘枚举问题非常相似(如果不完全相同)，由 John McCarthy 于 1977 年处理，其 gopher 函数做了完全相同类型的节点重新排列(树旋转到正确)正如这里提出的 tail^(**) 会那样.

update: A historical note: this is actually quite similar (if not exactly the same) as the efficient tree-fringe enumeration problem, dealt with in 1977 by John McCarthy, whose gopher function did exactly the same kind of nodes re-arrangement (tree rotations to the right) as the proposed here tail^(**) would.

这篇关于差异列表的显式纯函数数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！