阿娜/变质只是变慢了吗？

Question

写完this article后，我决定把钱放在嘴边，并开始将我以前的一个项目转换为使用recursion-schemes。

所讨论的数据结构是一个lazy kdtree。请查看使用explicit和implicit递归的实现。

这基本上是一种直截了当的转换，大意是：

data KDTree v a = Node a (Node v a) (Node v a) | Leaf v a

至

data KDTreeF v a f = NodeF a f f | Leaf v a

现在，在对整个shebang进行基准测试之后，我发现KDTreeF版本大约比普通版本(find the whole run here)慢两倍于。

仅仅是附加的Fix包装让我在这里慢下来了吗？我能做些什么来对付这件事吗？

注意事项：

• 目前，这是专门为(V3双)。
• 这是猫-后变质的应用。同胚不适用于树形。
• 我多次使用cata (fmap foo algebra)。这是很好的做法吗？
• 我使用爱德华兹recursion-schemes软件包。

编辑1：

这是相关的吗？https://ghc.haskell.org/trac/ghc/wiki/NewtypeWrappers是newtype Fix f = Fix (f (Fix f))不是“免费”吗？

编辑2：

刚刚又做了一堆基准。这一次我测试了树的构造和解构。基准测试：https://dl.dropboxusercontent.com/u/2359191/2014-05-15-kdtree-bench-03.html

虽然核心输出表明中间数据结构没有被完全删除，线性搜索现在占主导地位也就不足为奇了，但是KDTreeF现在比KDTree稍微快了一点，但并不重要。

Answer 1

我刚刚实现了树的Thing + ThingF + Base instance变体。你猜怎么着。这个速度快得惊人。

我的印象是，这将是所有变体中最慢的。我真该看看我自己的帖子..。我写的那一行：

找不到TreeF结构的跟踪

让数字代表自己，kdtreeu是新的变体。结果并不总是像这些情况那样清楚，但在大多数情况下，它们至少与显式递归(基准中的kdtree)一样快。

​

​

Answer 2

我不是使用递归方案，而是使用我自己的“手卷”cata、ana、Fix/unFix来生成(列表)和用一种小语言对程序进行评估，希望找到一个匹配(输入、输出)对的列表。

在我的经验中，cata比直接递归优化得更好，并且提高了速度。此外，IME，ana防止堆栈溢出错误，我的天真的生成器是造成，但使中心围绕生成的最终列表。

所以，我的回答是，不，它们并不总是慢的，但是我没有看到任何明显的问题；所以在你的情况下，它们可能会慢一些。递归方案本身也可能没有对速度进行优化。