为什么你可以用foldl来反转列表，但是不能用Haskell中的foldr [英] Why can you reverse list with foldl, but not with foldr in Haskell

问题描述

为什么你可以使用foldl来取消列表？

  reverse':: [a]  - > [a] 
 reverse'xs = foldl（\acc x-> x：acc）[] xs 
  

但是这个给了我一个编译错误。

  reverse':: [a]  - > [a] 
 reverse'xs = foldr（\acc x-> x：acc）[] xs 
  

$

 无法与实际类型为[[a]'$ b的预期类型'a'匹配$ b`a'是一个刚性类型变量，由
绑定，反向的类型签名为':: [a]  - > [a] at foldl.hs：33：13 
相关绑定包括
x :: [a]（绑定在foldl.hs：34：27）
 acc :: [a]（bound 
 xs :: [a]（bound to foldl.hs：34：10）
 reverse':: [a]  - > 
在`（:)'的第一个参数中，即`x'
在表达式中：x：acc 
  code> 




解决方案

首先，类型签名不会排队：

  foldl ::（o  - > i  - > o） - > o  - > [i]  - > o 
 foldr ::（i  - > o  - > o） - > o  - > [i]  - > o 
  

因此，如果您交换参数名称：

  reverse'xs = foldr（\ x acc  - > x：acc）[] xs 
  

现在编译。它不会工作，但它现在编译。

事情是， foldl ，从左向右（即向后）工作，而 foldr 从右向左（即向前）工作。这就是为什么 foldl 可以让你反转一个列表;它说明了所有这一切，你可以做

  reverse'xs = foldr（\ x acc  - > acc ++ [x]）[] xs 
  

然而，它会很慢。 （二次复杂度，而不是线性复杂度。）

Why can you reverse a list with the foldl?

reverse' :: [a] -> [a]
reverse' xs = foldl (\acc x-> x : acc) [] xs

But this one gives me a compile error.

reverse' :: [a] -> [a]
reverse' xs = foldr (\acc x-> x : acc) [] xs

Error

Couldn't match expected type `a' with actual type `[a]'
`a' is a rigid type variable bound by
  the type signature for reverse' :: [a] -> [a] at foldl.hs:33:13
Relevant bindings include
x :: [a] (bound at foldl.hs:34:27)
acc :: [a] (bound at foldl.hs:34:23)
xs :: [a] (bound at foldl.hs:34:10)
reverse' :: [a] -> [a] (bound at foldl.hs:34:1)
In the first argument of `(:)', namely `x'
In the expression: x : acc

解决方案

For a start, the type signatures don't line up:

foldl :: (o -> i -> o) -> o -> [i] -> o
foldr :: (i -> o -> o) -> o -> [i] -> o

So if you swap your argument names:

reverse' xs = foldr (\ x acc -> x : acc) [] xs

Now it compiles. It won't work, but it compiles now.

The thing is, foldl, works from left to right (i.e., backwards), whereas foldr works right to left (i.e., forwards). And that's kind of why foldl lets you reverse a list; it hands you stuff in reverse order.

Having said all that, you can do

reverse' xs = foldr (\ x acc -> acc ++ [x]) [] xs

It'll be really slow, however. (Quadratic complexity rather than linear complexity.)

这篇关于为什么你可以用foldl来反转列表，但是不能用Haskell中的foldr的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！