haskell 数据类型内部的惰性

vshtjzan  于 12个月前  发布在  其他
关注(0)|答案(2)|浏览(110)

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

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

字符串
直观地说,我认为Haskell会这样做:“我需要weird的第一个元素。我需要第一个元素的头。所以我需要计算fst weird。现在我知道fst weird = [1] ++ fst weird(或者我??)从对的半群示例。所以这很好,我应该返回1
我哪里搞错了?

nmpmafwu

nmpmafwu1#

这里的错误在于模式匹配。实际上,如果我们查看二元组示例[src]的Semigroupinstance,我们会看到:

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

字符串
所以这里它需要两个2元组,然后它将合并组合这两个。但这意味着它在第一个 * 和 * 第二个操作数上进行模式匹配。对于第二个操作数,有问题,因为这是计算的结果,所以触发系统评估这些。
这种匹配看起来可能是不必要的,但是传递undefined或其他一些导致循环的机制是可能的,就像这里所做的那样,因此代码基本上要求检查第二个操作数是否是二元组。
我们可以做的是使用 * irrefutable * 模式,这样我们就可以假设数据构造函数成立,并且只有在必要的时候才解压缩它。所以我们可以自己实现某种求和:

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


然后我们自己的实现工作:

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


所以我们使实现更懒惰地合并组合两个2元组。
我个人认为Semigroup s等在2-tuple(和任何 * n *-tuple)上的组合可以用不可反驳的模式来完成。我不知道是否有很好的理由为什么在基本包中不是这样。

jslywgbw

jslywgbw2#

正如已经解释过的,问题是<>对pairs是严格的。
解决这个问题的一种方法是以一种更明确的方式“lazify”结果。
例如,

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

字符串
由于~(x,y)中的惰性模式匹配,lazify在需要weird的递归之前产生顶级对构造函数(_, _)
lazify也可以等价地定义为lazify p = (fst p, snd p)。请注意它看起来像对上的恒等式,但它并不完全是恒等式:输出(_, _)是在 * 检查输入之前 * 产生的。为了强调这一点,这不会 * 崩溃:

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


事实上,这从来没有强迫undefined
一开始可能会很混乱,因为我们需要记住在什么时候计算什么。就个人而言,我相信理论在这里有很大的帮助。lambda演算与递归(PCF)的指称语义,以及它所有的CPO底部,在我看来很好地解释了结果。

相关问题