haskell - 为什么 haskell 的 `fix` 似乎对元组有问题？

Question

我试图围绕固定点和递归定义弯曲我的头。

这有效：

>>> take 10 $ let x = (0:x) in x
[0,0,0,0,0,0,0,0,0,0]

这做同样的事情，考虑到 的定义，这是有道理的fix：

>>> take 10 $ fix (\x -> (0:x))
[0,0,0,0,0,0,0,0,0,0]

现在假设我开始使用递归定义的对：

>>> take 10 $ fst $ let (u,v) = (0:v,1:u) in (u,v)
[0,1,0,1,0,1,0,1,0,1]

好吧，我应该也能写出来fix，对吧？

>>> take 10 $ fst $ fix (\(u,v) -> (0:v,1:u))
*** Exception: <<loop>>

但它不起作用。除非我做出以下看似微不足道的改变：

>>> take 10 $ fst $ fix (\r -> let (u,v)=r in (0:v,1:u))
[0,1,0,1,0,1,0,1,0,1]

最后两个示例之间的关键区别是什么？

Answer 1

你要

take 10 $ fst $ fix (\ ~(u,v) -> (0:v,1:u))
                      ^^^

从而使模式匹配变得懒惰。在let中，LHS 模式是隐含的惰性/无可辩驳的。

使用plain \(u,v) -> ...，在产生任何输出之前将需要lambda的参数——这使得函数对于fix. 你需要的是类似

take 10 $ fst $ fix (\p -> (0:snd p,1:fst p))

这样参数就不会被 lambda 强制（没有构造函数可以匹配）。惰性模式方法等价于fst/snd上述方法。