数据类型内部的惰性

Question

我以为我很好地理解了惰性，直到我想出了下面的代码，它产生了一个<<loop>>错误。

weird = ([1],[2]) <> weird
main = print (head $ fst weird)

直观上，我认为 Haskell 会这样做：“我需要 的第一个元素weird。而且我需要第一个元素的头。所以我需要计算。现在我从对的半群实例中fst weird知道（或者我是吗？？） fst weird = [1] ++ fst weird. 太好了，我该回来了1”

我哪里弄错了？

Answer 1

这里是模式匹配出了问题。事实上，如果我们查看2 元组实例\xc2\xa0 ^[src]instance的ofSemigroup，我们会看到：

\n

\n

instance (Semigroup a, Semigroup b) => Semigroup (a, b) where\n    (a,b) <> (a\',b\') = (a<>a\',b<>b\')\n    stimes n (a,b) = (stimes n a, stimes n b)\n

\n

\n

所以这里需要两个 2 元组，然后它将两者结合起来。但这意味着它会在第一个和第二个上进行模式匹配模式匹配。对于第二个操作数，存在问题，因为这是计算的结果，因此会触发系统评估这些操作数。

\n

匹配可能看起来没有必要，但可能会传递undefined或其他一些导致循环的机制，就像这里所做的那样，因此代码基本上要求检查第二个操作数是否是 2 元组。

\n

我们能做的是使用无可辩驳的模式，这样我们就假设数据构造函数保存并且仅在必要时将其解压。所以我们可以自己实现某种求和：

\n

(<^>) :: (Semigroup a, Semigroup b) => (a, b) -> (a, b) -> (a, b)\n~(a,b) <^> ~(a\',b\') = (a<>a\',b<>b\')

\n

然后我们自己的实现适用于：

\n

weird = ([1],[1]) <^> weird\nmain = print (head $ fst weird)\n

\n

所以我们让实现更加懒惰地组合两个二元组。

\n

Semigroup就我个人而言，我认为2 元组（以及任何n元组）上 s 等的组合可以通过无可辩驳的模式来完成。我不知道是否有充分的理由说明基础包中的情况并非如此。

\n

Answer 2

正如已经解释的，问题在于<>对成对的限制。

解决该问题的一种方法是以更明确的方式“惰性化”结果。

例如，

weird = lazify $ ([1],[1]) <> weird
   where lazify ~(x,y) = (x,y)

由于在需要递归之前lazify生成了顶级对构造函数，因此可以工作，这要归功于 中的惰性模式匹配。(_, _)weird~(x,y)

lazify也可以等价地定义为lazify p = (fst p, snd p). 请注意，它看起来像对上的恒等式，但它并不完全是恒等式：输出是在检查输入之前(_, _)生成的。强调一点，这不会崩溃：

case lazify (undefined :: (Int, Int)) of
   (_x, _y) -> 42

事实上，这永远不会强制undefined.

一开始可能会很混乱，因为需要记住在什么时间评估什么。就我个人而言，我相信理论在这里有很大帮助。在我看来，带有递归的 lambda 演算 (PCF) 的指称语义及其所有带有底部的 CPO 很好地解释了结果。