How to get generic (polymorphic) lambda in scala?

Question

Update (2018): my prayers were answered in Dotty (Type Lambdas), so the following Q&A is more "Scala 2.x"-related

---

Just a simple example from Scala:

scala> def f(x: Int) = x
f: (x: Int)Int

scala> (f _)(5)
res0: Int = 5

Let's make it generic:

scala> def f[T](x: T) = x
f: [T](x: T)T

scala> (f _)(5)
<console>:9: error: type mismatch;
 found   : Int(5)
 required: Nothing
              (f _)(5)
                    ^

Let's look at eta-expansion of polymorphic method in Scala:

scala> f _ 
res2: Nothing => Nothing = <function1>

Comparison with Haskell:

Prelude> let f x = x

Prelude> f 5
5
Prelude> f "a"
"a"
Prelude> :t f
f :: t -> t

Haskell did infer correct type [T] => [T] here.

More realistic example?

scala> identity _
res2: Nothing => Nothing = <function1>

Even more realistic:

scala> def f[T](l: List[T]) = l.head
f: [T](l: List[T])T

scala> f _
res3: List[Nothing] => Nothing = <function1>

You can't make alias for identity - have to write your own function. Things like [T,U](t: T, u: U) => t -> u (make tuple) are impossible to use as values. More general - if you want to pass some lambda that rely on generic type (e.g. uses generic function, for example: creates lists, tuples, modify them in some way) - you can't do that.

So, how to solve that problem? Any workaround, solution or reasoning?

P.S. I've used term polymorphic lambda (instead of function) as function is just named lambda

Answer 1

Only methods can be generic on the JVM/Scala, not values. You can make an anonymous instance that implements some interface (and duplicate it for every type-arity you want to work with):

trait ~>[A[_], B[_]] { //exists in scalaz
  def apply[T](a: A[T]): B[T]
}

val f = new (List ~> Id) {
  def apply[T](a: List[T]) = a.head
}

Or use shapeless' Poly, which supports more complicated type-cases. But yeah, it's a limitation and it requires working around.

Answer 2

P∀scal is a compiler plugin that provides more concise syntax for encoding polymorphic values as objects with a generic method.

The identity function, as a value, has type ∀A. A => A. To translate that into Scala, assume a trait

trait ForAll[F[_]] {
  def apply[A]: F[A]
}

Then the identity function has type ForAll[λ[A => A => A]], where I use the kind-projector syntax, or, without kind-projector:

type IdFun[A] = A => A
type PolyId = ForAll[IdFun]

And now comes the P∀scal syntactic sugar:

val id = Λ[Α](a => a) : PolyId

or equivalently

val id = ν[PolyId](a => a)

("ν" is the Greek lowercase letter "Nu", read "new")

These are really just shorthands for

new PolyId {
  def apply[A] = a => a
}

Multiple type parameters and parameters of arbitrary kinds are supported by P∀scal, but you need a dedicated variation on the above ForAll trait for each variant.

Answer 3

I really like @Travis Brown 's solution:

import shapeless._

scala> Poly(identity _)
res2: shapeless.PolyDefns.~>[shapeless.Id,shapeless.Id] = fresh$macro$1$2$@797aa352

-

scala> def f[T](x: T) = x
f: [T](x: T)T

scala> Poly(f _)
res3: shapeless.PolyDefns.~>[shapeless.Id,shapeless.Id] = fresh$macro$2$2$@664ea816

-

scala> def f[T](l: List[T]) = l.head
f: [T](l: List[T])T

scala> val ff = Poly(f _)
ff: shapeless.PolyDefns.~>[List,shapeless.Id] = fresh$macro$3$2$@51254c50

scala> ff(List(1,2,3))
res5: shapeless.Id[Int] = 1

scala> ff(List("1","2","3"))
res6: shapeless.Id[String] = 1

Poly constructor (in some cases) will give you eta-expansion into Shapeless2 Poly1 function, which is (more-less) truly generic. However it doesn't work for multi-parameters (even with multi type-parameters), so have to "implement" Poly2 with implicit + at approach (as @som-snytt suggested), something like:

object myF extends Poly2 {
  implicit def caseA[T, U] = at[T, U]{ (a, b) => a -> b}
}

scala> myF(1,2)
res15: (Int, Int) = (1,2)

scala> myF("a",2)
res16: (String, Int) = (a,2)

P.S. I would really want to see it as a part of language.

Answer 4

It seems to do this you will need to do a bit type hinting to help the Scala type inference system.

def id[T] : T => T = identity _

So I guess if you try to pass identity as a parameter to a function call and the types of that parameter are generic then there should be no problem.