concat中foldRight和foldLeft之间有什么区别

Question

为什么我不能在以下代码中使用fold Left:

def concatList[T](xs: List[T],ys:List[T]): List[T]=
     (xs foldLeft ys)(_::_)

实际上我很难理解foldRight和foldLeft之间的区别,有没有例子来说明真正的差异？

谢谢.

Answer 1

好吧,你可以,

scala> def concatList[T](xs: List[T],ys:List[T]) = 
         (xs foldLeft ys)( (a, b) => b :: a )
concatList: [T](xs: List[T], ys: List[T])List[T]

scala> concatList(List(1,2,3), List(6,7,8))
res0: List[Int] = List(3, 2, 1, 6, 7, 8)

那是你期待的结果吗？我不这么认为.

首先让我们看一下折叠的签名和::(仅用于说明目的的简化,但完全符合我们的情况):

given a List[T]
  def ::(v:T): List[T] // This is a right associative method, more below
  def foldLeft[R](r:R)(f: (R,T) => R):R
  def foldRight[R](r:R)(f: (T,R) => R):R

现在,在foldLeft中应用一个参数列表,xs.foldLeft(ys)并从foldLeft示例调用中统一我们签名中的类型:

List [T]:List [Int],因此T:Int和R:List [Int],应用于foldLeft签名给出

foldLeft[List[Int]](r:List[Int])( f:(List[Int],Int) => List[Int] )

现在,的用法::,a :: b编译成b.::(a),斯卡拉往往是指它作为一个右结合的方法.这是一个特殊的语法糖,用于结束:定义列表时非常方便的方法:1 :: 2 :: Nil就像写作一样Nil.::(2).::(1).

继续我们的实例化foldLeft,我们需要传递的函数必须如下所示:(List[Int],Int) => List[Int].考虑一下(a,b) => a :: b,如果我们将其与我们f得到的类型统一起来:

一个:列表[INT] ,和B:诠释,比较与的签名a2 :: b2,A2的:int,B2:列表[INT] .为了编译,a和a2与b和b2一起必须具有相同的类型.他们没有!

请注意,在我的示例中,我反转了参数,使匹配类型为b2,b匹配a2的类型.

我将提供另一个编译的版本:

def concatList[T](xs: List[T],ys:List[T]) = (xs foldLeft ys)( _.::(_) )

要简短地讲述故事,请查看foldRight签名

def foldRight[R](r:R)(f: (T,R) => R):R

参数已被反转,因此制作f = _ :: _给出了正确的类型.

哇,这是关于类型推断的很多解释,我很及时,但我还是要解释左右折叠的含义之间的区别.现在看看https://wiki.haskell.org/Fold,特别是这两个想象:

请注意,foldl和foldr的参数是反转的,它首先将函数和它们r作为签名中的初始参数,而不是::仅用于列表构造:.两个非常小的细节.