How can I compose generic methods in Scala?

Question

I'm learning Scala and have the following toy code:

object M {
  def isSorted[X](xs: Array[X], compare: (X, X) => Boolean): Boolean =
    xs.dropRight(1).zip(xs.drop(1)).forall(Function.tupled(compare))

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

My goal is to call it like:

M.curry(M.isSorted)(Array(1,2,3))((a, b) => a < b)

But I receive the error:

scala> M.curry(M.isSorted)(Array(1,2,3))
<console>:8: error: type mismatch;
  found   : Int(1)
  required: Nothing
  M.curry(M.isSorted)(Array(1,2,3))

Let's back up and look at the type of the curried function:

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

That's no good. It wants an Array[Nothing] but there can be no instances of Nothing.

I understand at some point I will need to introduce a constraint so the compiler can prove that the expression a < b is allowable; that is, that a and b are Ordered. But I don't know where I would put the constraint. curry is perfectly generic; the constraint doesn't belong there. isSorted knows nothing about the implementation of compare, so it doesn't belong there either.

The closest I've gotten to having it working is with def isSorted[X >: Any]

scala> M.curry(M.isSorted)(Array(1,2,3))((a, b) => a < b)
<console>:8: error: value < is not a member of Any
  M.curry(M.isSorted)(Array(1,2,3))((a, b) => a < b)
                                                ^

scala> M.curry(M.isSorted)(Array(1,2,3))((a: Int, b: Int) => a < b)
<console>:8: error: type mismatch;
  found   : (Int, Int) => Boolean
  required: (Any, Any) => Boolean
  M.curry(M.isSorted)(Array(1,2,3))((a: Int, b: Int) => a < b)
                                                          ^

How can I get this working?

Answer 1

object M {
  def isSorted[X](xs: Array[X], compare: (X, X) => Boolean): Boolean =
    xs.dropRight(1).zip(xs.drop(1)).forall(Function.tupled(compare))

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

Well... I don't think this is the best way to define these functions but in this case, since these are generic functions so you need to provide them with a type when calling.

As @dk14 has pointed out in his comment... M.sorted can not get type info because Scala lacks support for polymorphic lambdas.... which simply means no generics in anonymous functions.

So you need to do this for this particular case.

M.curry( M.isSorted[Int] )( Array(1,2,3) ) ( (a , b) => a < b )