标签: finger-tree

Clojure的新contrib库组有一个手指树 库.在clojure中手指树有什么用例？什么时候应该使用手指树而不是clojure的其他持久数据结构之一:向量,集合,映射,持久性等等.

Clojure的喜悦提到手指树可以用于需要廉价插入和删除的索引集合.它们也被描述为"数据结构的瑞士军刀".非常感谢这方面的例子.

该Applicative实例Data.Sequence通常性能非常好。几乎所有的方法在时间和空间上都是渐进渐近最优的。也就是说，给定完全强制/实现的输入，可以在渐近最优的时间和内存驻留中访问结果的任何部分。还有一个例外：(<*). 我目前只知道两种实现方式：

1. 默认实现

   xs <* ys = liftA2 const xs ys
   

   Run Code Online (Sandbox Code Playgroud)

   这个实现需要O(|xs| * |ys|)时间和空间来完全实现结果，但只O(log(min(k, |xs|*|ys|-k)))访问k结果的第 th 个元素。

2. “一元”实现

   xs <* ys = xs >>= replicate (length ys)
   

   Run Code Online (Sandbox Code Playgroud)

   这只需要O(|xs| * log |ys|)时间和空间，但它不是增量的；访问结果的任意元素需要O(|xs| * log |ys|)时间和空间。

长期以来，我一直认为应该有可能拥有我们的蛋糕并吃掉它，但我从来没有能够很好地处理我脑海中的碎片以达到目标。要做到这一点似乎需要从的实现思路（而不是实际的代码）的组合liftA2和replicate。如何才能做到这一点？

注意：它肯定不会有必要结合像什么rigidify的机制liftA2。类似replicate的部分肯定应该只产生我们rigidify用来从用户提供的树中获得的那种“刚性”结构。

更新（2020 年 4 月 6 日）

任务完成！我设法找到了一种方法。不幸的是，这对我来说有点太复杂了，无法理解正在发生的一切，而且代码……相当不透明。我会赞成并接受对我所写内容的一个很好的解释，并且也会很高兴地接受关于 GitHub …

不久之前,我遇到了一篇关于FingerTrees的文章(另见附带的Stack Overflow问题),并提出了这个想法.我终于找到了使用它们的理由.

我的问题是,Data.FingerTree软件包似乎在边缘有点腐烂.此外,Containers包中的Data.Sequence使用数据结构重新实现(可能更好)版本,但不导出它.

由于理论上这个结构似乎很有用,但它似乎没有得到很多实际使用或关注.有人发现FingerTrees作为一个实际问题没有用处,或者这是一个不够关注的案例？

进一步说明:

我有兴趣构建一个包含具有良好串联属性的文本的数据结构.考虑从各种片段构建HTML文档.大多数预构建的解决方案使用字节串,但我真的想要正确处理Unicode文本的东西.我的计划是将Data.Text片段分层到FingerTree中.

我还想借用Data.Vector借用切片而无需使用(偏移,长度)操作进行复制.Data.Text.Text内置于数据类型,但仅用于高效的uncons和unsnoc opperations.在FingerTree中,这些信息很容易成为v树的注释或注释.

显然Seq渐近地执行与[]所有可能操作相同或更好的操作.但由于它的结构比列表更复杂,对于小尺寸,它的恒定开销可能会使它变慢.我想知道多少,特别是:

1. 如何慢得多的<|比较:？
2. Seq与折叠/遍历相比,折叠/遍历的速度要慢多少[](不包括折叠/遍历功能的成本)？
3. 大小(大约)\xs x -> xs ++ [x]变得比|>什么慢？
4. 大小(大约)++变得比><什么慢？
5. viewl与列表上的模式匹配相比,结果上的调用和模式匹配的成本是多少？
6. 与元素列表相比,n元素Seq占用了多少内存n？(不计算元素占用的内存,只计算结构.)

我知道这很难衡量,因为Seq我们谈论摊销的复杂性,但我想知道至少一些粗略的数字.

昨天的Wikibender以Comonads上的stackoverflow问题开始,最终出现在MarkCC关于Finger Trees 的文章中.

在文章中,他广泛使用了Reduce类型类.他写了关于这个类型类的文章,好像它是一个非常常见且经常使用的库,但我无法在hackage上找到它,也无法找到足够的文档来真正理解代码.

有人可以帮助我理解Reduce类型类正在做什么,(-<)和(>-)运算符如何工作,以及应该告诉我文章中的代码(下面复制)？

从手指树完成的代码清单(我希望):

清单1:Node的实例声明

instance Reduce Node where
  reducer (-<) (Node2 a b) z = a -< (b -< z)
  reducer (-<) (Node3 a b c) z = a -< (b -< (c -< z))
  reducer (>-) (Node2 b a) = (z >- b) >- a
  reducer (>-) (Node3 c b a) = ((z >- …

我正在寻找一个持久的顺序数据结构,允许有效的随机插入和删除.我找到了以下实现:

• clojure.data.finger-tree(计数双列表实现)
• wgjo.data.cljs
• flexvec

由于没有在clojure.data.finger树在过去两年多的活动,和其他人都比较新,我在想,如果有人在生产中使用任何这些中的遭遇,以及是否有我的选择忽视.

我想用2-3个手指树来玩,如Hinze的(Haskell)论文所述(另见本博客).

type Node<'a> =
    | Node2 of 'a * 'a
    | Node3 of 'a * 'a * 'a

    static member OfList = function
        | [a; b] -> Node2(a, b)
        | [a; b; c] -> Node3(a, b, c)
        | _ -> failwith "Only lists of length 2 or 3 accepted!"

    member me.ToList () =
        match me with
        | Node2(a, b) -> [a; b]
        | Node3(a, b, c) -> [a; b; c]

type Digit<'a> =
    | One of …

我想要一个具有快速连接和编辑操作的字符串表示.我读过"绳索:弦乐的替代品"这篇论文,但自1995年以来,这个领域有没有重大改进？

编辑:我之前考虑过的一种可能性是使用带有字符串作为树叶的2-3指树,但我还没有对此进行详细分析; 这给出了在末端的摊销的恒定时间添加/删除和对数(在较小的串的块的数量中)连接,而不是相反的绳索.

我已经google了一下,发现了一篇关于Finger Trees的文章,它可用于实现具有适当渐近复杂度的优先级队列,但它们非常复杂,但仍然是我能找到的最简单的东西.

是否有一个简单的数据结构允许在Haskell中实现快速优先级队列？ 想简单在你能解释给新手程序员.