sweetyBaby - 1 year ago 116
Scala Question

# What 's the difference between foldRight and foldLeft in concat

Why I cannot use fold Left in the following code:

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

Actually it is hard for me to understand the differences between foldRight and foldLeft, it there any examples to illustrate the real differences?

Thanks.

Well, you can,

``````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)
``````

Was that the result you were expecting? I don't think so.

First let's look at the signature of the folds and `::` (only a simplification for illustrative purposes, but fits perfectly in our case) :

``````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
``````

Now, apply one argument list in foldLeft we `xs.foldLeft(ys)` and unifying the types from our signature from foldLeft sample call:

List[T] : List[Int], therefore T : Int, and R : List[Int], that applied to foldLeft signature gives

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

Now, for the usage of `::`, `a :: b` compiles to `b.::(a)`, Scala often refers to it as a right associative method. This a special syntax sugar for methods ending in `:` and quite convenient when defining a list: `1 :: 2 :: Nil` is like writing `Nil.::(2).::(1)`.

Continuing our instantiation of `foldLeft`, the function we need to pass has to look like this: `(List[Int],Int) => List[Int]`. Consider `(a,b) => a :: b`, if we unify that with the type of we `f` get:

a : List[Int], and b : Int, comparing that with the signature of `a2 :: b2`, a2 : Int, b2 : List[Int]. For this to compile, a and a2 in conjunction with b and b2 must have the same types each. Which they don't!

Notice in my example, I inverted the arguments, making a match the type of b2 and b match the type of a2.

I will offer yet another version that compiles:

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

To cut the story short, look at foldRight signature

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

The arguments are already inverted, so making `f = _ :: _` gives us the right types.

Wow, that was a lot of explanation about type inference and I am sort on time, but I still owe a explanation on difference between the meaning of fold left and right. For now have a look at https://wiki.haskell.org/Fold, in special these two imagines:

Notice, the argument to foldl and foldr are inverted, it first takes the function and them the inital arguments, `r` in the signatures, and instead of `::` for list construction it uses just `:`. Two very small details.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download