Why does foldLeft make use of a partial function?

[Haddock]

hello,

another beginner question... foldLeft makes use of a partial function:

def foldLeft[B](z: B)(f: (B, A) => B): B = {
...
}

My question is what the gain is in doing so. I thought the gain is that you can use wildcards as in this (I mean the "_ + _" thing):

val list = List(1, 1, 1, 1)
list.foldLeft(0){_ + _}

But this seems not to be the case. When I define a fold method without a partial function:

def fold(coll: List[Int], seed: Int, block: (Int, Int) => Int) : Int = {
    var acc = seed
    var these = coll
    while (!these.isEmpty) {
      acc = block(acc, these.head)
      these = these.tail
    }
    acc
  }

I can still use wildbards as this here compiles and runs correctly:

val list = List(1, 1, 1, 1)
val res = fold(list, 0, {_ + _})

Thanks for any input.
Cheers, Haddock

[Harald Meland]

On Tue, Jan 6, 2015 at 1:32 PM, Haddock <ffm...@web.de> wrote:

hello,

another beginner question... foldLeft makes use of a partial function:

No; I suspect that your usage of the term "partial function" actually is a reference to the use of more than one argument list.  This is confusing, as Scala has a separate concept named PartialFunction; see http://www.scala-lang.org/api/current/index.html#scala.PartialFunction .

One reason for writing foldLeft with multiple argument lists is to help the Scala compiler's type inference.  As your version of fold() does not employ any type arguments, it does not show any such inference troubles.  However:

scala> def fold[A, B](coll: List[A], seed: B, block: (B, A) => B): B = {

     |     var acc = seed
     |     var these = coll
     |     while (!these.isEmpty) {
     |       acc = block(acc, these.head)
     |       these = these.tail
     |     }
     |     acc
     |   }

fold: [A, B](coll: List[A], seed: B, block: (B, A) => B)B

scala> fold(List(1,1,1,1), 0, { _ + _ } )
<console>:9: error: missing parameter type for expanded function ((x$1, x$2) => x$1.$plus(x$2))
              fold(List(1,1,1,1), 0, { _ + _ } )
                                       ^
<console>:9: error: missing parameter type for expanded function ((x$1: <error>, x$2) => x$1.$plus(x$2))
              fold(List(1,1,1,1), 0, { _ + _ } )
                                           ^

isn't as smooth as it could be, while

scala> def fold[A, B](coll: List[A], seed: B)(block: (B, A) => B): B = {

     |     var acc = seed
     |     var these = coll
     |     while (!these.isEmpty) {
     |       acc = block(acc, these.head)
     |       these = these.tail
     |     }
     |     acc
     |   }

fold: [A, B](coll: List[A], seed: B)(block: (B, A) => B)B

scala> fold(List(1,1,1,1), 0)( _ + _ )
res2: Int = 4

works without having to be explicit about any type arguments.

--

Harald

[Haddock]

Hi Harald,

thanks for the reply. Must have been long ago that I read about partial functions. So I messed it up completely. Your point that it is about helping the compiler to infer types is interesting.

In Kotlin there is the corresponding method fold that takes the closure named operation as an argument:

public fun <T, R> Iterable<T>.fold(initial: R, operation: (R, T) -> R): R

Apparently, Kotlin does not have problems to infer the type.

-- Haddock

[Naftoli Gugenheim]

Scala's "problem" is the flip side of a feature: All the arguments in a given argument list contribute to inferring the type parameters simultaneously. The conclusions are then used as a premise when interpreting the next argument list.

Curious: Does Kotlin work that way? Or does Kotlin infer one single argument at a time?

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Haddock]

Curious: Does Kotlin work that way? Or does Kotlin infer one single argument at a time?

That I don't know. But Kotlin can't do this { _ + _  } thing as Scala can. Maybe that has to do with it.

-- Haddock

[Haddock]

By the way harald was right. This here does not compile:

def fold[T](coll: List[T], seed: T, block: (T, T) => T) : T = {
    // ...
  }

fold(list, 0, (a, b) => a + b) // compiler error: missing parameter type (that is for a and b).

While this here compiles fine:

def fold2[T](coll: List[T], seed: T) (block: (T, T) => T) : T = {
   // ...
}

fold2(list, 0)((a, b) => a + b)

So it is about type inference...

[Jon Pretty]

Hi Haddock,

Type inference in Scala works by typechecking each parameter *block* in turn, so in `fold2`, the type `T` is worked out based on the first parameter block, the least upper bound of `T` from the parameters `coll` and `seed`, and after that `T` is known and fixed. For the second parameter block, the partial function only needs to be checked as consistent with `T`; it's not being used to infer the type `T`.

The problem with the `fold` method is that Scala can't infer the domain (i.e. `(T, T)`) from a partial function literal. This often confuses people. But say, for example, that the function were this:

   { (a, b) => a + b.toInt }

which is identical to

   { _ + _.toInt }

(The underscores are pure syntactic sugar.)

This would be consistent if `T` were `Double` or `String`, which are unrelated types. Even if it could analyze, from the code, that it's a type with both a `toInt` and a `+` method on it, the compiler is no closer to knowing `T`. And, in general, it can't.

And because it can't work out this type for this one parameter, it can't work out the least upper bound of `T` for the entire expression, because `block`, along with `coll` and `seed`, necessarily contributes to that calculation of `T`.

Hope that helps!

Cheers,
Jon

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

Jon Pretty | @propensive