Bruno Oliveira Bruno Oliveira - 3 months ago 21
Scala Question

Partial Function Application in Scala

I'm learning Functional Programming, by following the book Functional Programming in Scala by Paul Chiusano and Rúnar Bjarnason. I'm specifically on chapter 3, where I am implementing some companion functions to a class representing a singly-linked list, that the authors provided.

package fpinscala.datastructures

sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head: A, tail: List[A]) extends List[A]

object List {
def sum(ints: List[Int]): Int = ints match {
case Nil => 0
case Cons(x,xs) => x + sum(xs)
}

def product(ds: List[Double]): Double = ds match {
case Nil => 1.0
case Cons(0.0, _) => 0.0
case Cons(x,xs) => x * product(xs)
}

def apply[A](as: A*): List[A] =
if (as.isEmpty) Nil
else Cons(as.head, apply(as.tail: _*))

def tail[A](ls: List[A]): List[A] = ls match {
case Nil => Nil
case Cons(x,xs) => xs
}
... (more functions)
}


The functions I am implementing go inside the object List, being companion functions.

While implementing dropWhile, whose method signature is:

def dropWhile[A](l: List[A])(f: A => Boolean): List[A]


I came across some questions regarding partial function application:

In the book, the authors say that the predicate, f, is passed in a separate argument group to help the scala compiler with type inference because if we do this, Scala can determine the type of f without any annotation, based on what it knows about the type of the List , which makes the function more convenient to use.

So, if we passed f in the same argument group, scala would force the call to become something like this:
val total = List.dropWhile(example, (x:Int) => 6%x==0 )
where we define the type of x explicitly and we would "lose" the possibility of partial function application, am I right?

However, why is partial function application useful in this case? Only to allow for type inference? Does it make sense to "partially apply" a function like dropWhile without applying the predicate f to it? Because it seems to me that the computation becomes "halted" before being useful if we don't apply f...

So... why is partial function application useful? And is this how it's always done or is it only something specific to Scala? I know Haskell has something called "complete inference" but I don't know exactly its implications...

Thanks in advance

Answer

There's a couple of questions scattered in there, so I'll try to answer them separately.

About the type inference, yes, separating the parameter lists helps the compile in inferring the type of f.

This is because Scala has linear local type inference (from left to right) and it uses the first parameter list to infer A (from the type of l). Then it can use this information to infer the type of f.

Given for example

dropWhile(List(1, 2, 3))(x => x < 3)

the compiler will perform this steps:

  • first parameter list

    • A is unknown.
    • a List[A] is expected
    • a List[Int] is provided (this is inferred by the type of the elements in the List)
    • => A is an Int
  • second parameter list

    • we know A = Int
    • so we're expecting a function Int => Boolean as f

If you don't separate the two parameter lists, the compiler can't "stop" and decide the type of A before type-checking f. f would be part of the "conversation" while deciding the type of A so you would need to annotate it.

This is something Haskell can do better, since it uses a different type system (Hindley-Milner) that can also use information deriving from the context in which the function is applied. This is why it's also called "complete" or "universal".

Why does Scala doesn't feature an Hindley-Milner type system? Long story short, because Scala also supports sub-typing, which hardly co-exists with such a powerful type system. More on the subject:

About partial application, the question "why is it useful" is definitely too broad to be answered here. However, in the specific dropWhile case, suppose you have a list of functions representing different "drop" conditions. Using a partially applied function you could do:

val list = List(1, 2, 3)
val conditions: List[Int => Boolean] = List(_ < 1, _ < 2, _ < 3)
conditions.map(dropWhile(list)) // List(List(1, 2, 3), List(2, 3), List(3))

Obviously, with a non-curried function (i.e. a single parameter list) you could have achieved the same with

val list = List(1, 2, 3)
val conditions: List[Int => Boolean] = List(_ < 1, _ < 2, _ < 3)
conditions.map(cond => dropWhile(list, cond))

but currying allows for more flexibility while composing functions.

More on the subject:

Comments