程序员经验分享-hwhale

为什么 FingerTrees 没有得到足够的使用来实现稳定的实现？

2024-01-08

前段时间，我遇到了关于 FingerTrees 的文章 http://scienceblogs.com/goodmath/2010/04/finger_trees_done_right_i_hope.php（也可以看看附带的堆栈溢出问题 https://stackoverflow.com/questions/8450448/finding-the-missing-reduce-typeclass-from-finger-tree-article）并将这个想法归档。我终于找到了使用它们的理由。

我的问题是Data.FingerTree 包 http://hackage.haskell.org/package/fingertree-0.0.1.0边缘似乎有点腐烂。而且，数据序列 http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Sequence.html在使用数据结构的 Containers 包中重新实现 http://www.haskell.org/ghc/docs/latest/html/libraries/containers/src/Data-Sequence.html#line-259一个（可能更好）版本，但不导出它。

尽管这种结构在理论上似乎很有用，但它似乎并没有得到太多的实际使用或关注。人们是否发现 FingerTrees 在实际中没有什么用处，或者这是一个没有引起足够重视的情况？

进一步解释:

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

我还想借用 Data.Vector 的技巧，即在不使用（偏移量，长度）操作进行复制的情况下进行切片。 Data.Text.Text 将此内置到数据类型中，但仅将其用于高效的 uncons 和 unsnoc 操作。在 FingerTree 中，这些信息很容易成为v或树的注释。


特别要回答关于手指树的问题，我认为问题在于与数组相比，它们具有相对较高的恒定成本，并且比实现高效串联的其他方法更复杂。构建器有一个更有效的接口，用于仅附加块，并且它们通常很容易获得（请参阅@informatikr的答案中的链接）。假设Data.Text.Lazy是用块的链接列表实现的，并且您正在创建一个Data.Text.Lazy来自建筑商。除非您有很多块（可能超过 50 个），或者重复访问列表末尾附近的数据，否则手指树的高恒定成本可能不值得。

The Data.Sequence出于性能原因，实现是专门的，并且不像 提供的完整接口那么通用fingertree包裹。这就是为什么它不被导出；除了Sequence.

我还怀疑许多程序员不知道如何实际使用幺半群注释，因为它背后有一个相当重要的抽象障碍。很多人不会使用它，因为他们不知道它与其他数据类型相比有何用处。

直到读了 Chung-jieh Shan 的博客系列后我才真正明白字数 http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WordNumbers1/ (part2 http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WordNumbers2/, part3 http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WordNumbers3/, part4 http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WordNumbers4/）。这证明这个想法绝对可以在实际代码中使用。

在您的情况下，如果您需要检查部分结果并进行有效的附加，那么使用 Fingertree 可能比构建器更好。根据构建器的实现，当您转换为Text，向构建器添加更多内容，转换为Text再次等等。但这取决于您的使用模式。

您可能对我的感兴趣展开树 http://hackage.haskell.org/package/splaytree包，它提供了带有幺半群注释的展开树，以及在它们之上构建的几种不同的结构。除了伸展树本身之外，Set and RangeSet模块具有或多或少完整的 API，Sequence模块主要是我用于测试的骨架。它不是您正在寻找的“包含电池”的解决方案（同样，@informatikr 的答案提供了这些），但如果您想尝试幺半群注释，它可能比Data.FingerTree。请注意，如果按顺序遍历所有元素（或不断地插入末尾，或类似的），展开树可能会变得不平衡，但如果追加和查找是交错的，则性能可能会非常好。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Haskell

datastructures

fingertree

为什么 FingerTrees 没有得到足够的使用来实现稳定的实现？ 的相关文章

  • 公式的后序遍历

    在数据结构中 我将按顺序转换和预排序公式转换为树 不过 我不太擅长后期订购 对于给定的公式x y z a b c 我想出了 divide x c y z a b 在大多数情况下 这似乎很合适 除了左子树中的 是牌组中的小丑 在后序遍历中 最

  • Haskell：需要了解 Functor 的签名

    有人能给我解释一下 Functor 的签名吗 Prelude gt info Functor class Functor f gt where fmap a gt b gt f a gt f b lt a gt f b gt f a 我不明

  • 在 Haskell 中获取玫瑰树的根

    最近我开始学习 Haskell 并在以下练习中遇到困难 Write functions root Rose a gt a and children Rose a gt Rose a that return the value stored

  • Control.Parallel.Strategies 中 Eval 的绑定运算符如何严格评估其参数？

    Control Parallel Strategies 的源代码 http hackage haskell org packages archive parallel 3 1 0 1 doc html src Control Paralle

  • 迭代和遍历有什么区别？

    过去几周我一直在学习迭代器 我仍然不明白迭代链接列表和遍历链接列表之间的主要区别 我知道遍历意味着遍历 访问每个元素 链接列表 并且在迭代时基本上做同样的事情 但是有什么不同 为什么不能遍历所有内容 标准库数据结构 遍历 只是意味着遍历数据

  • 在 Haskell 中将字符串转换为整数/浮点数？

    data GroceryItem CartItem ItemName Price Quantity StockItem ItemName Price Quantity makeGroceryItem String gt Float gt I

  • 如何在 Haskell Pipes 中将两个 Consumer 合并为一个？

    我使用Haskell流处理库pipes https hackage haskell org package pipes编写一个命令行工具 每个命令行操作都可以将结果输出到stdout并记录到stderr with pipes API I n

  • O(n^2) 与 O (n(logn)^2)

    时间复杂度是O n 2 or O n logn 2 better 我知道当我们简化它时 它就变成了 O n vs O logn 2 and logn lt n 但是关于logn 2 n is only less than log n 2 f

  • 如何让 do 块提前返回？

    我正在尝试使用 Haskell 抓取网页并将结果编译到一个对象中 如果出于某种原因 我无法从页面获取所有项目 我想停止尝试处理页面并提前返回 例如 scrapePage String gt IO scrapePage url do doc

  • Data.Array 有多快？

    The 文档 http haskell org ghc docs latest html libraries array 0 3 0 3 Data Array html of Data Array reads Haskell 提供了可索引数

  • Python OO程序结构规划

    我是 OOP 的初学者 我想创建一个包含三个类 A B 和 C 的程序 该类的每个实例都由一组特征 Achar1 Achar2 等定义 该程序应该创建uses由 A 元素 B 元素和 C 元素以及开始日期和结束日期组成 A 和 B 都有子类

  • 我可以从 GHCi 中找到 GHC 版本吗？

    gt 我在里面输入什么GHCi发现它正在使用哪个 GHC 版本 gt import System Info gt browse arch String compilerName String compilerVersion Data Ver

  • 使用 Parsec 解析正则表达式

    我正在尝试通过实现一个小型正则表达式解析器来学习秒差距 在 BNF 中 我的语法类似于 EXP EXP LIT EXP LIT 我尝试在 Haskell 中实现这一点 expr try star lt gt try litE lt gt l

  • 这是 unsafeCoerce 的安全使用吗？

    我遇到的情况是 我目前正在使用极其可怕的函数 unsafeCoerce 幸运的是 这并不是为了任何重要的事情 但我想知道这是否是该函数的安全使用 或者是否有其他方法可以解决其他人知道的这个特定问题 我的代码类似于以下内容 data Toke

  • 与 Functor 不同，Monad 可以改变形状？

    我一直很喜欢以下关于单子相对于函子的力量的直观解释 单子可以改变形状 函子不能 例如 length fmap f 1 2 3 总是等于3 然而 对于单子来说 length 1 2 3 gt gt g往往不等于3 例如 如果g定义为 g Nu

  • Haskell数据类型转换问题

    我目前正在学习 Haskell 并且一直在编写一些非常简单的程序来练习 我的程序之一是 import System IO main do putStrLn Give me year y lt getLine let res show cal

  • 在 Archlinux 上使用 Vim 作为 Haskell 的 IDE 目前情况如何？

    如果可行的话 我的目标是通过 YouCompleteMe 在 Vim 中完成 Haskell 的命令 在这方面 正如您在下面看到的 我还没有找到关于如何让它发挥作用的共识 相关评论的最新评论YouCompleteMe 上的问题 https

  • Haskell 为替代的 Either 数据类型定义 Functor 实例

    通过 Typeclassopedia 获得一些使用类型类的路由 想要替代Either的一个实例Functor 但即使检查定义Either作为一个例子Functor总是给我带来麻烦 有这个 但不会编译 data Alt a b Success

  • 在ghci中，如何删除现有的绑定？

    我收到一个 绑定影响现有绑定 错误 类似于以下错误this https stackoverflow com questions 2902716 in haskell what does it mean if a binding shadow

  • Cabal 无法安装依赖项，但如果直接询问可以安装它们

    我发现 Cabal 反复出现一个非常奇怪的问题 它影响了我获得可重复的 Haskell 构建的能力 我有一个带有沙箱的阴谋集团项目 如果我做cabal install 我收到以下形式的错误 Y failed during the build

随机推荐

  • 如何增加UIProgressView的高度

    我正在创造UIProgressView from nib 我想增加它的高度 但它固定为 9 对于iPad我需要增加它的高度 怎样才能做到呢 使用 CGAffineTransform 更改尺寸 CGAffineTransform transf

  • 哪个先出现——finally 还是 catch 块？

    考虑以下测试用例 public class Main static int a 0 public static void main String args try test System out println test2 catch Ex

  • 获取 og:image 元属性的最佳方法是什么[重复]

    这个问题在这里已经有答案了 我正在尝试在我的网站中显示 rss feed 链接 一切顺利 但需要很长时间才能获得og image财产通过使用file get contents 方法 还有其他方法可以获取元标记属性吗 Python 有助于更快

  • 如何将 JSONObject 转换为自定义 Java 类？

    在Java中 使用 json simple https code google com p json simple 我已经成功解析了使用 JSON stringify 在 JavaScript 中创建的 JSON 字符串 它看起来像这样 t

  • 所有 SuppressWarnings 值？ [复制]

    这个问题在这里已经有答案了 如果有一个包含可以与 java 中的 SuppressWarnings 一起使用的所有值的列表 那就太好了 如果这些值取决于编译器 可以说 netbeans 中的 ant 那么 ant 不应该提供所有支持值的完整

  • 执行 expo build:ios 时 Apple Developer Portal 中的身份验证失败

    我正在尝试自动配置通过 Gitlab CI 使用 Expo 构建 iOS 应用程序 这是我正在使用的命令 expo login u expo user p expo pass expo build ios non interactive a

  • JSF MVC 框架中的 MVC 是什么组件？

    JSF MVC框架中谁是模型 视图和控制器 这取决于观点 双关语 在总体架构图中 您自己的 JSF 代码是V M 业务领域 服务层 例如EJB JPA DAO V 您的 JSF 代码 C FacesServlet 在开发人员图中 架构V又可

  • 为什么 ASCII 表中大写字母位于小写字母之前？

    在我的一次面试中 面试官问我为什么ASCII表中大写字母在小写字母之前 我在google com上搜索但没有找到任何结果 有人能给我答案吗 多谢 我只是猜测 但我想这是因为最早的字符集根本没有小写字母 Baudot 电报码只有 5 位 CD

  • 从图像文件夹加载数组 - xcode

    我在将图像从文件加载到数组中时遇到一些问题 我使用了我在这里找到的问题的组合 但我没有想法 我对 Objective C 很陌生 对其余的都生疏了 我的 viewDidLoad 只是调用我的 showPics 方法 并且为了测试目的 我让

  • 如何在map函数中使用useEffect？

    我在 Firebase 中有两个表 Vouchers 和 ClaimedVouchers 我正在尝试显示未出现在 ClaimedVouchers 表中的优惠券 因此 我有一个查询获取所有优惠券 然后另一个查询检查它们是否已被认领 如果已认领

  • docker数据量与挂载的主机目录

    我们可以在docker中拥有一个数据卷 docker run v path to data in container name test container debian docker inspect test container Moun

  • 如何结合 constexpr 和矢量化代码？

    我正在为 x64 和 neon 开发 C 内在包装器 我希望我的函数是 constexpr 我的动机类似于Constexpr 和 SSE 内在函数 https stackoverflow com questions 51880079 con

  • 如何让 foo.somedomain.com 由 appengine 上的 myapp.appspot.com/foo 处理

    这就是我想要实现的目标 http foo somedomain com http foo somedomain com被处理http myapp appspot com foo http myapp appspot com foo 谷歌应用

  • Python 值错误：没有足够的值来解压

    代码中出现以下错误 不确定这意味着什么或我做错了什么 只是尝试将三个列表值初始化为空集合 nba nfl mlb ValueError not enough values to unpack expected 3 got 0 问题是 左侧值

  • Nokogiri 支持哪个版本的 xpath？

    我找不到 Nokogiri 支持的 xpath 版本的官方声明 有人可以帮我吗 事实上 我想提取一些具有以指定子字符串开头的属性的元素 例如 我想获得所有Book元素具有category属性以字符开头C 如何使用 nokogiri 做到这一

  • 确定 R 中的嵌套级别？

    有没有一种简单的方法 即函数 来确定列表中的嵌套级别 我知道有str可以用来获取此信息 但有没有什么东西可以简单地返回结果呢 我可以使用这样的函数来获取所有级别的名称 递归 吗 一个小的递归函数可以为你做到这一点 depth lt func

  • 找不到已连接的设备。模拟器启动失败：无法通过提供的索引或标识符解析指定的连接设备。

    我正在学习 NativeScript 并且 跑步时tns platform add android我收到以下错误 我按照这个步骤 以管理员身份运行命令提示符 powershell NoProfile ExecutionPolicy unre

  • 如何在 React Redux 应用程序中使用装饰器？

    我正在使用 React Redux 创建简单的应用程序 我想使用装饰器在我的组件中注入一些方法 我在其他项目中看到了类似的代码 import React Component from react import connect from re

  • 新自我与新静态

    我正在将 PHP 5 3 库转换为在 PHP 5 2 上工作 阻碍我的主要事情是使用后期静态绑定 例如return new static options 如果我将其转换为return new self options 我会得到相同的结果吗

  • 为什么 FingerTrees 没有得到足够的使用来实现稳定的实现？

    前段时间 我遇到了关于 FingerTrees 的文章 http scienceblogs com goodmath 2010 04 finger trees done right i hope php 也可以看看附带的堆栈溢出问题 htt

热门标签