这些关于折叠和递归的前提是否正确？

Question

当使用foldr时，递归发生在函数内部，所以，当给定的函数没有严格评估双方时，并且可以return在第一个的基础上，foldr一定很好解决，因为它适用于 无限列表

findInt :: Int -> [Int] -> Bool
findInt z [] = False
-- The recursion occours inside de given function
findInt z (x:xs) 
  | z == x = True
  | otherwise = findInt z xs

相当于：

findInt' :: Int -> [Int] -> Bool
findInt' z = foldr (\x r -> if z == x then True else r) False
-- Where False is the "default value" (when it finds [], ex: findInt z [] = False)

foldr不合适的情况：

addAll :: Int -> [Int] -> Int
addAll z [] = z
-- The recursion occours outside the given function (+)
addAll z (x:xs) = addAll (z + x) xs

在这种情况下，因为 + 是严格的（需要评估双方 return）如果我们能以某种方式应用它，那将会非常有用有一个 redex (reducible expression)，可以避免 thunks 并且（当被迫运行之前的评估时，不是懒惰的 ） space 并且没有太多压入堆栈 （类似于命令式算法中for循环的优点）

addAll' :: Int -> [Int] -> Int
addAll' z [] = z
addAll' z (x:xs) = let z' = z + x
                  in seq z' $ addAll' z' xs

相当于：

addAll'' :: Int -> [Int] -> Int
addAll'' z = foldl' (+) z

在这种小情况下，使用 foldr（内部递归）没有意义因为它不会产生氧化反应。它会是这样的：

addAll''' :: Int -> [Int] -> Int
addAll''' z [] = z
addAll''' z (x:xs) = (+) x $ addAll''' z xs

这道题的主要objective先，知道我的前提是不是正确 或者他们 可以做得更好的地方 其次，帮助 使其更清晰对于也在学习 Haskell 的其他 内部和内部的差异外部递归，在这些方法中，要清楚哪一个可能更适合特定情况

有用的链接：

Haskell Wiki

Whosebug - Implications of foldr vs. foldl (or foldl')

Answer 1

除了 foldr 是列表的自然变形而 foldl 和 foldl' 不是这一事实之外，还有一些使用指南：

你是正确的，foldr 总是 return，即使在无限列表中，只要函数在其第二个参数中是非严格的，因为列表的元素立即可用于函数的第一个参数（与 foldl 和 foldl' 不同，后者的列表元素在列表被完全消耗之前不可用于函数的第一个参数）；
foldl' 将是非无限列表的更好选择，如果你想确保常数 space，因为它是尾递归的，但 它总是解析整个列表，不管严格评估传递给它的函数的参数；
一般来说，foldr相当于递归，而foldl和foldl'相当于循环；
由于 foldr 是自然变形，如果您的函数需要重新创建列表（例如，如果您的函数只是列表构造函数':'），foldr 会更合适；
关于 foldl 与 foldl'，foldl' 通常更可取，因为它不会构建巨大的 thunk，但是，如果传递给它的函数在其第一个参数中不是严格的并且列表不是无限的，foldl可能 return 而 foldl' 可能会报错（Haskell wiki 中有一个很好的例子）。

附带说明一下，我相信您使用术语 "inside recursion" 来定义 foldr 并使用 "outside recursion" 来定义 foldl 和 foldl'，但我之前从未在文献中看到过这些术语.更常见的是，这些函数分别被称为从右折叠和从左折叠，这些术语虽然可能不完全正确，但它们很好地说明了列表元素传递给函数的顺序。

这些关于折叠和递归的前提是否正确？

Are these premises about folds and recursion right?

recursion

haskell

lazy-evaluation

fold