递归或折叠 haskell

Question

我正在使用 haskell 学习一些函数式编程，我正在尝试通过重新实现一些库函数来了解一些概念。

我有一个问题，但主要是关于何时选择递归而不是迭代更好。例如，当重新实现 "all" 函数时，我可以选择：

all1 :: (a -> Bool) -> [a] -> Bool
all1 p xs = foldr (\x acc -> acc && p x) True xs 

all2 :: (a -> Bool) -> [a] -> Bool
all2 p (x:xs) 
  | p x == False = False
  | otherwise    = all2 p xs

在我看来，递归应该更省时，因为它会在第一个不匹配的条目处停止，而折叠式更 space 有效（我认为，仍然不是清楚 haskell 中的尾递归优化），但它将始终扫描完整列表，除非通过查看 false 总是给出 false 的事实来进行一些巧妙的优化.

那么，这种妥协是一直存在的吗？我是否误解了递归和折叠工作的方式？

Answer 1

foldr定义如下：

foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

如果将此定义内联到 all1，您会发现结果也是递归的。因此，它不是显式递归，因为它隐藏了 foldr.

内部的递归

foldr 变体更 space 高效且更节省时间，因为 foldr 具有 list fusion 的规则（删除中间列表的优化），这all1 免费获得。

要使短路工作，只需将 acc && p x 更改为 p x && acc。使用 foldr，这将在获得 False 结果后立即停止遍历列表。使用 foldl 或 foldl'，即使你的折叠功能短路，它仍然需要遍历列表的其余部分。

总结：使用 foldr 比 foldl、foldl' 或在您自己的函数中显式递归更有效。一个很好的简单测试是在 GHCi 中执行 +set :s，然后比较列表 (False:replicate 10000000 True).

上的性能

Answer 2

让我们逐块考虑一下基于 foldr 的解决方案是否可以短路。首先，(&&) 定义为 like this:

(&&)                    :: Bool -> Bool -> Bool
True  && x              =  x
False && _              =  False

鉴于第二个子句，由于懒惰，如果第一个参数是 False，(&&) 的第二个参数将被忽略——换句话说，它短路了。

接下来，this is foldr for lists：

foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

如果y `k` go ys不用看go ys就可以求值，不会有递归调用，fold整体会shortcut

在all1中，二元运算为\x acc -> acc && p x。这对于我们的目的来说还不够好，因为 acc（对应 foldr 定义中的 go ys）作为 (&&) 的第一个短路参数导致整个列表被消耗，而不管 p x 结果是什么。不过，并非所有内容都丢失了：将参数交换为 (&&)...

all3 :: (a -> Bool) -> [a] -> Bool
all3 p xs = foldr (\x acc -> p x && acc) True xs

...给了我们想要的短路。

递归或折叠 haskell

Recursion or fold in haskell

recursion

haskell

lazy-evaluation