使用foldl和foldr计算长度

Question

我有两个函数用于计算整数列表的长度。

lengthFoldl :: [Int] -> Int
lengthFoldl xs = (foldl (\_ y -> y+1) 0 xs)

并且

lengthFold :: [a] -> Int
lengthFold xs = foldr (\_ y -> y+1) 0 xs

它们是相同的，只是一个使用了foldr，另一个使用了foldl。

但是当尝试计算任何列表[1 .. n]的长度时，我从lengthFoldl得到了一个错误的结果（比实际长度多1）。

- förschter

---

尝试运行 lengthFoldl [42]。 - n. m.

@n.m. 你的意思是 lengthFoldl [41]。42 应该是 答案。 :) :) - Will Ness

Answer 1

为了补充joelfischerr的回答，我想指出你的函数类型可以给出一些提示。

lengthFoldl :: [Int] -> Int
lengthFold :: [a] -> Int

为什么它们不同？我猜你可能需要将第一个更改为使用[Int]，因为使用[a]无法编译。然而，这是一个很大的警告信号！

如果它确实计算长度，那么为什么lengthFoldl要关心列表元素的类型是什么呢？我们为什么需要元素是Int？Int被需要的唯一解释是看代码。

lengthFoldl xs = foldl (\_ y -> y+1) 0 xs

我们可以看到，这里唯一的数值变量是y。如果强制y为数字，并将列表元素也强制为数字，似乎y就被视为列表元素！

实际上就是这种情况：foldl先将累加器传递给函数，然后是列表元素，与foldr不同。

一般的经验法则是：当类型和代码不相符时，应仔细考虑哪个是正确的。我会说大多数Haskeller会认为，在大多数情况下，更容易得到正确的类型而不是正确的代码。因此，不能只是调整类型以强制编译：类型错误可能反映出代码中的错误。

- chi

---

谢谢！这是一个很好的思考方式。 - förschter

Answer 2

看一下 foldl 和 foldr 的类型定义，就可以明白问题所在了。

:t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

并且。

:t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

可以看出，foldr将列表项和第二个参数传入函数中，而foldl将第二个参数和列表项传入函数中。

将lengthFoldl更改为以下内容即可解决问题。

lengthFoldl :: [Int] -> Int
lengthFoldl xs = foldl (\y _ -> y+1) 0 xs

编辑：使用foldl而不是foldl'是一个坏主意：https://wiki.haskell.org/Foldr_Foldl_Foldl

- förschter

---

对我来说，使用 foldl 时，通过始终使用 \acc a -> ... 来处理这些事情在心理上更容易处理；而使用 foldr 时，则通过始终使用 \a r -> ... 来处理这些事情在心理上更容易处理。顺便提一下，你几乎总是想使用 foldl'（而不是 foldl）。 - Will Ness

为什么我应该使用 foldl？ - förschter

foldl'（而非 foldl）更加严格。您的 foldl 不会在遍历列表时实际计算求和，而是只是存储未来要进行的加法操作。这会导致内存膨胀，如果列表太长，甚至可能导致栈溢出，因为那些嵌套的未来加法操作必须被回溯并实际计算。 我会找到官方链接并很快添加在这里。在这里。 - Will Ness