sweetyBaby - 1 year ago 87

Scala Question

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.

Answer Source

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.