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 模式是隐含的懒惰/无可辩驳的。

与平原 \(u,v) -> ...在产生任何输出之前将要求 lambda 的参数——这使得函数对于 fix 来说过于严格.你需要的是类似

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

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