Curry in scala with parametric types

Question

The authors of Functional Programming in Scala give this as the definition of curry in scala:

def curry[A,B,C](f: (A, B) => C): A => (B => C) =
    a => b => f(a, b)

However, if we apply it to a function taking parametric types, e.g.:

def isSorted[A](as: Array[A], ordered:(A,A)=>Boolean) =
    if(as.size < 2)
        true else
           as.zip(as.drop(1)).map(ordered.tupled).reduce(_ && _)

Then the result wants A (in isSorted) to be nothing:

scala> curry(isSorted)
res29: Array[Nothing] => (((Nothing, Nothing) => Boolean) => Boolean) = <function1>

This is obviously not what is desired. Should curry be defined differently, or called differently, or is it not practical to implement curry in Scala?

so you want to test your isSorted method? – Maytham Fahmi Mar 19 '16 at 20:51 — Maytham Fahmi, Mar 19 '16 at 20:51
No, I want to use curry for functions with type parameters. – Marcin Mar 19 '16 at 20:53 — Marcin, Mar 19 '16 at 20:53

score 3 · Answer 1 · edited May 23 '17 at 12:31

3

It turns out I can call curry like this:

curry(isSorted[Int])

Which yields:

scala> curry(isSorted[Int])
res41: Array[Int] => (((Int, Int) => Boolean) => Boolean) = <function1>

See https://stackoverflow.com/a/4593509/21640

edited May 23 '17 at 12:31

Community

1
1

answered Mar 19 '16 at 20:54

Marcin

48,559
18
128
201

score 3 · Accepted Answer · answered Mar 20 '16 at 03:58

You're running into two separate problems here. The first is that isSorted when it is passed to curry is forced to become monomorphic. The second is that Scala's type inference is failing you here.

This is one of those times where the difference between a function and a method matters in Scala. isSorted is eta-expanded into a function which in turn is a Scala value, not a method. Scala values are always monomorphic, only methods can be polymorphic. For any method of types (A, B) C (this is the syntax for a method type and is different from (A, B) => C which is a function and therefore a value), the default eta-expansion is going to result in the superclass of all functions of that arity, namely (Nothing, Nothing) => Any. This is responsible for all the Nothings you see (you don't have any Anys because isSorted is monomorphic in its return value).

You might imagine despite the monomorphic nature of Scala values though, that you could ideally do something like

def first[A, B](x: A, y: B): A = x
curry(first)(5)(6) // This doesn't compile

This is Scala's local type inference biting you. It works on separate parameter lists from left to right first is the first thing to get a type inferred and as mentioned above, it gets inferred to be (Nothing, Nothing) => Any. This clashes with Ints that follow.

As you've realized, one way of getting around this is annotating your polymorphic method that you pass to curry so that it eta-expands into the correct type. This is almost certainly the way to go.

Another thing you could possibly do (although I'm don't think it'll serve anything except pedagogical purposes) is to curry curry itself and define it as follows:

def curryTwo[A, B, C](x: A)(y: B)(f: (A, B) => C): C = f(x, y)

On the one hand, the below works now because of the left-to-right type inference.

curryTwo(5)(6)(first) // 5

On the other hand, to use curryTwo in the scenarios where you'd want to use curry, you're going to need to need to provide types to Scala's type inference engine anyway.

Thank you! This is extremely educational. – Marcin Mar 20 '16 at 14:37 — Marcin, Mar 20 '16 at 14:37

Curry in scala with parametric types

2 Answers2