loeb如何在这个haskell示例中终止？

Question

从这个Youtube视频:

> let loeb fs = xs where xs = fmap ($ xs) fs
> loeb [length, (!! 0)]
[2,2]

在xs这里是递归定义的,以及如何勒布终止我是无法理解.

Answer 1

试试吧:

loeb [length, (!! 0)]
= xs where xs = fmap ($ xs) [length, (!! 0)]
= xs where xs = [length xs, xs !! 0]

所以当然length xs只有2,所以xs(length xs)的第一个元素也是2.

记住:length xs不需要评估列表中的项目:

length [undefined, undefined] = 2

Answer 2

原因是length不评估列表的元素.它只是计算元素.length是(语义等价)定义为:

length (_:xs) = 1 + length xs
length _ = 0

即使其中一个元素因此计算出导致无限循环的表达式,也无关紧要.只要列表本身当然不是无限的.

现在你打电话loeb [length, (!! 0)],它将被评估为:

loeb [length, (!! 0)]
    xs = fmap ($ xs) [length,(!! 0)]
    xs = [length xs,xs !! 0]

因此length xs执行延迟评估:它对元素的值不感兴趣,因此在计数时它们仍未解决.