15

我看过很多演讲/阅读博客文章，您应该有严格的字段data以避免各种性能问题，例如：

data Person = Person
    { personName     :: !Text
    , personBirthday :: !UTCTime
    }

这对我来说完全有意义。由于对该数据的函数操作是惰性的，因此不会牺牲可组合性。

但是，如果我添加一个Maybe字段：

data Person = Person
    { personName     :: !Text
    , personBirthday :: !UTCTime
    , personAddress  :: !(Maybe Address)
    }

我在数据结构中引入了惰性，毕竟Maybe是一个控制结构。未评估的 thunk 不能隐藏在Just构造函数后面吗？

但是，有严格Maybe的 in strictor thru strict-base-types。但是根据反向依赖（strict，strict-base-types），它们并没有被广泛使用。

那么问题来了：为什么应该或不应该Maybe在非控制数据定义中使用严格？

4

2 回答 2

3

并不是“严格就是快，懒就是慢”那么简单。

懒惰和严格都有利于性能提升；让我们看看懒惰是怎样的：

  • 如果列表是严格的，则显然sum $ take 10 $ [1..]需要无限的时间和无限的内存，但如果列表是惰性的，则需要有限的时间和恒定的内存。

  • 函数式数据结构通常不承认良好的摊销界限。什么是“摊销”界限？当你只在 O( n ) 其他完全不相关的步骤之后支付 O( f ( n )) 的成本时，我们可以想象地将其重新概念化为为这些步骤中的每一个支付 O( f ( n )/ n )：所以如果你例如，将n 个元素添加到列表中，然后在n log n时间内对其进行一次排序，然后您可以重新概念化为每次添加都需要 log n时间。（如果您使用自平衡二叉搜索树而不是列表来支持它，它会这样做，但我们可以说即使有一个列表，成本也是 log n摊销。）

    将其与函数式编程结合起来的问题是，当我给你一个新的数据结构时，旧的数据结构不会被修改，所以作为一般理论的一点，如果转换一些 X 的成本很高，那么存在一个有效的使用模式，它像以前一样花费n努力来构建 X，但随后以不同的方式使用它m次（因为它没有被修改！）每次都会产生 O( f ( n )) 成本：所以现在当你尝试摊销你只会得到 O( m f ( n )/ n )，如果m与n成比例，您已经从为整个结构产生一次此成本转变为每次添加到数据结构时基本上产生一次。当您创建数据结构时，您不能说“哦，那不是我的用例”：即使它不是您的，也可能是其他人的，最终说起来。

    Okasaki 指出（在他的论文 (PDF)中）惰性（带有记忆化）实际上正是我们需要弥合这个差距的：假设X将其后处理版本存储为惰性值，那么对 transform X 的每次调用都会命中相同的惰性值并产生相同的记忆答案。所以：如果你能巧妙地将这些东西移动到 thunk 中，那么 Haskell 不会重新计算 thunk 的事实可以用来制作记忆参数。

  • 再举一个例子，++在 Haskell 中是一个 O(1) 操作；使用严格列表将大小为n的列表附加到大小为m的列表的末尾需要预先分配O( m ) 内存，因为前面的列表需要完全重建；流连接将其转换为 O( m ) 条件操作（幸运的是，它与处理器中的分支预测器配合得非常好！）并将此成本分配给列表的每次读取。

  • 如果您不使用大量数据，但您不知道您正在使用哪些东西，那么懒惰具有很大的潜力。举一个简单的例子，如果你必须反复反转一些难以在某个有界区间上预测的昂贵单调函数，你可能没有一个封闭形式的逆或函数或其导数的快速表达式（以便使用牛顿-拉夫森）。相反，您可以构建一个恒定深度的大二叉搜索树，其节点用f ( x ) 注释，叶子代表x；然后你通过计算f ( x _) 和二进制搜索x。然后，每个查询都会被自动记忆，因此搜索靠近其他查询的值会由于相同的缓存而获得渐近加速（以不断增加的内存为代价）。

那么，什么时候严格有帮助呢？

您想要消除惰性的真实情况是递归数据结构，即使那样，这也仅适用于您知道您希望整个数据结构在内存中可用（即您将使用所有数据结构）。这样的数据结构通常是脊椎严格的：例如，一个包含实际值的 thunk 的列表，但指向其他列表节点的指针都是 100% 严格的。

当这些条件都为真时，将惰性放在每个节点上没有真正意义，因为它提供了额外的 O( n ) 成本来评估所有这些 thunk，并且可能会将调用堆栈炸毁到递归限制，如果你不要使用严格性注释来降低它。如果您对此不是 100% 清楚，那么我所看到的关于这种情况如何发生的最好解释就是这样的，证明在两者都因不同原因溢出调用堆栈的foldl'情况下的必要性。foldrfoldl这些解释通常非常实用。

严格也可以把一大堆成本放在前面，比如当你想做一个游戏时：如果你懒惰地生成游戏世界，那么当你走进一个全新的区域时，你可能会注意到“缓冲”；但是如果你可以严格提前生成这些东西，你必须付出早期的成本，但你会得到后期的收益。当他们点击“加载游戏”按钮时，人们不介意等待，当它打破沉浸在某个故事中时，他们真的很讨厌等待。（实际上并行懒惰是真正理想的：您希望能够在需要之前在后台强制执行 thunk，同时动作更轻一些，以便在您想要的时候获得结果。甚至然后，虽然 - 我的意思是，这就是TES3：Morrowind的工作方式，但是它们包含了一组卷轴作为堵嘴，如果你能在着陆中幸存下来，它可以让你在游戏世界中跳跃一半——而你在这样做时获得的速度意味着你飞越这些区域的速度比系统可以加载它们，所以它会不断地给你 3 秒的空中飞行时间，然后停下来说“加载中……”，一遍又一遍，当你以这种方式穿越游戏世界时。没有什么能真正阻止这个问题。）

当我需要修复它时，我该如何修复它？

所以：我们了解到，一个典型的Maybe地方不会为您的应用程序创造可观的成本。这就是为什么没人在乎。

当我们创建一个递归数据结构时，比如另一种列表类型data NonNullList x = NNL x !(Maybe (NonNullList x))，它必须总是至少有一个元素怎么办？在这种情况下，递归存在于 Maybe中，我们如何解决这个问题？

是的，您可以使用严格的 Maybe。但是，您也可以内联结构以使其严格。在这种情况下，你会写：

data NonNullList x = End x | Continue x !(NonNullList x)

如果你的数据结构中有太多的重复信息（也许我们在数据结构中存储了很多元数据）和太多的Maybe (MyDataStructure x)调用，那么我们最终可能必须有一个data MyDataStructureDescriptor = MDSD { property1 :: !String, property2 :: !Int, ...}这样的描述符的重复次数可以减少到一种常见的格式。这实际上也非常适合组织您的代码。

于 2016-01-07T17:11:28.030 回答
2

使用严格的 Either/Maybe/Tuple 类型的原因：

  • 如果您分析您的代码并注意到空间泄漏，这可能是堵塞泄漏的方法

  • 严格的数据类型被广泛认为对高性能代码有用，即使是最新的 GHC 8.0 语言扩展

  • 其他人也在这样做（那些严格的包可能不受欢迎，但它们的存在是有原因的——你也可以争辩说，你需要这些严格的包的那种应用程序可能不会上传到 Hackage）

没有的原因：

总的来说，我不认为教条会以这样或那样的方式发展。这只是一个方便的问题。

于 2016-01-07T15:43:53.113 回答