首页 文章

为什么这个Haskell代码能够成功地使用无限列表？

提问于
浏览 次
31

我有一些Haskell代码在无限列表中正常工作，但我不明白为什么它可以成功地这样做 . （我修改了我原来的代码 - 没有处理无限列表 - 在网上加入其他代码的东西，突然间我发现它有效，但不知道为什么） .

myAny :: (a -> Bool) -> [a] -> Bool
myAny p list = foldr step False list
   where
      step item acc = p item || acc

我对foldr的理解是它将遍历列表中的每个项目（也许这种理解是不完整的） . 如果是这样，那么“步”函数的表达方式无关紧要......代码应该无法处理无限循环 .

但是，以下工作：

*Main Data.List> myAny even [1..]
True

请帮我理解：为什么？

haskell functional-programming infinite fold

4 回答

  • 1

    让我们来看看Haskell如何评估你的表达 . 在每一行上用等于等于等于，表达式很快就会计算为True：

    myAny even [1..]
foldr step False [1..]
step 1 (foldr step False [2..])
even 1 || (foldr step False [2..])
False  || (foldr step False [2..])
foldr step False [2..]
step 2 (foldr step False [3..])
even 2 || (foldr step False [3..])
True   || (foldr step false [3..])
True

    这是有效的，因为 acc 作为未评估的thunk（延迟评估）传递，但也因为 || 函数在其 first 参数中是严格的 .

    所以这终止了：

    True || and (repeat True)

    但这不是：

    and (repeat True) || True

    看看||的定义看看为什么会这样：

    True  || _ =  True
False || x =  x
    回复于
  • 46

    我对foldr的理解是它将循环遍历列表中的每个项目（也许这种理解是不完整的） .

    foldr （与 foldl 不同）不必遍历列表中的每个项目 . 查看如何定义 foldr 是有益的 .

    foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

    当评估对 foldr 的调用时，它会强制评估对函数 f 的调用 . 但请注意对 foldr 的递归调用是如何嵌入函数 f 的参数中的 . 如果 f 不评估其第二个参数，则不会评估该递归调用 .

    回复于
  • 1

    这里的关键点是Haskell是一种非严格的语言 . “非严格”意味着它允许非严格的功能，这反过来意味着在使用之前可能无法完全评估功能参数 . 这显然允许延迟评估，这是“一种延迟计算直到需要结果的技术” .

    从this Wiki article开始

    回复于
  • 18

    我不知道Haskell，但我怀疑在你的情况下，它的作用是因为懒惰的评估 . 因为它允许您无限长地使用列表，所以当您访问它时，它将根据您的需要计算结果 .

    见http://en.wikipedia.org/wiki/Lazy_evaluation

    回复于

相关问题