Folding lists in scala

1
votes

Folding list in scala using /: and :\ operator

I tried to to look at different sites and they only talk about foldRight and foldLeft functions.

def sum(xs: List[Int]): Int = (0 /: xs) (_ + _)
sum(List(1,2,3))
res0: 6

The code segment works as described. But I am not able to completely understand the method definition. What I understand is that the one inside the first parenthesis -> 0 /: xs where /: is a right associate operator. The object is xs and the parameter is 0. I am not sure about the return type of the operation (most probably it would be another list?). The second part is a functional piece which sums its two parameters. But I don't understand what object invokes it ? and the name of function. Can someone please help me to understand.

2
scalafold
It looks like the code segment is not formatted correctly in my original post. The function definition is: def sum(xs: List[Int]): Int = (0 /: xs) (_ + _). The call is sum(List(1,2,3)). The result is: 6. - user3103957
/: is a (now deprecated) alias to foldLeft the same applies to :/ with foldRiight. If you look at the scaladoc you will see that both methods receive two parameters lists. One for the zero element of the folding. And the other for the aggregation function. - Luis Miguel Mejía Suárez
sure, thanks Luis! But I am trying to understand how to interpret the syntax. - user3103957
The code can be desugared as xs./:(0)(_ + _). Is a method with two parameters lists. Thus passing just one parameter is not really returning anything. Second because of many syntactic rules it can be called without the dot and passing first the zero element and then the collection and finally the function. But, as I said, the alias is deprecated, al most no body used it (except for haskallators), it caused confusions and it is hard to get the precedence right. I would not really care about it and just use foldLeft / foldRight instead. - Luis Miguel Mejía Suárez

2 Answers

2
votes

The signature of :/ is 

/:[B](z: B)(op: (B, A) ⇒ B): B

It is a method with multiple argument lists, so when it is just invoked with on argument (i.e. 0 /: xs in your case) the return type is (op: (B, A) ⇒ B): B. So you have to pass it a method with 2 parameters ( _ + _ ) that is used to combine the elements of the list starting from z.

This method is usually called foldLeft:

(0 /: xs)(_ + _) is the same as xs.foldLeft(0)(_ + _)

You can find more details here: https://www.scala-lang.org/api/2.12.3/scala/collection/immutable/List.html

0
votes

Thanks @HaraldGliebe & @LuisMiguelMejíaSuárez for your great responses. I am enlightened now!. I am just summarisig the answer here which may benefit others who read this thread.

"/:" is actually the name of the function which is defined inside the List class. The signature of the function is: /:[B](z: B)(op: (B, A) ⇒ B): B --> where B is the type parameter, z is the first parameter; op is the second parameter which is of functional type. The function follows curried version --> which means we can pass less number of parameters than that of the actual number. If we do that, the partially applied function is stored in a temporary variable; we can then use the temporary variable to pass the remaining parameters. If supplied with all parameters, "/:" can be called as: x./:(0)(_+_) where x is val/var of List type. OR "/:" can be called in two steps which are given as: step:1 val temp = x./:(0)(_) where we pass only the first parameter. This results in a partially applied function which is stored in the temp variable. step:2 temp(_+_) here using the partially applied function temp is passed with the second (final) parameter.

If we decide to follow the first style ( x./:(0)(_+_) ), calling the first parameter can be written in operator notion which is: x /: 0 Since the method name ends with a colon, the object will be pulled from right side. So x /: 0 is invalid and it has to be written as 0 /: x which is correct. This one is equivalent to the temp variable. On following 0 /: x, second parameter also needs to be passed. So the whole construct becomes: (0/:x)(_+_)

This is how the definition of the function sum in the question, is interpreted.

We have to note that when we use curried version of the function in operator notion, we have to supply all the parameters in a single go.

That is: (0 /: x) (_) OR (0 /: x) _ seems throwing syntax errors.