Why I cannot use fold Left in the following code:
def concatList[T](xs: List[T],ys:List[T]): List[T]=
(xs foldLeft ys)(_::_)
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
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
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.