Defining lift for all mappable types

Question

For the sake of my own curiosity, I tried to define Haskell's liftM for all types that define map[B](f : A => B): M[A], but couldn't get there on my own*. I was hoping that somebody with a deeper insight into Scala's type system might be able to explain it to me.

First I attempted to use structural type constraints:

import language.higherKinds
import language.reflectiveCalls
def lift[A, B, F[_] <: {def map(f : A => B): F[B]}](a : F[A])(g : A => B) =
  a map g

lift(Some(1)) {_ + 1} // error: inferred type arguments [Int,Nothing,Some] do not
                      // conform to method lift's type parameter bounds 
                      // [A,B,F[_] <: AnyRef{def map(f: A => B): F[B]}]

I've attempted a few other things in this vein, but could never get a function to accept a type defining map[B](f : A => B): F[B]. I also took a whack at it via traits:

object Liftable {
  import language.higherKinds

  trait Mappable[A, F[_]] {
    def map[B](f : A => B): F[B]
  }

  implicit class MappableOption[A](opt : Option[A]) extends Mappable[A, Option] {
    def map[B](f : A => B) = opt map f
  }

  def lift[A, B, F[_]](a : Mappable[A, F])(f : A => B) =
    a map f
}
import Liftable._

lift(Some(1)) {_ + 1}          // Some(2)
lift(None:Option[Int]) {_ + 1} // None

This works, but it would require defining an implicit class for every type that defines the map function. It loses a lot of it's usefulness there. I'm not sure if there's a way to define an implicit conversion for all types that define map - it brings me back to the problem I had with my first approach.

Am I overlooking something? Is the only viable way to do this to follow the second approach, and define an implicit conversion for each mappable type individually?

---

_{* I'm aware that the Scalaz library has some form of the lift function defined for its Functor trait, but I wasn't fully able to understand how it works in context with their entire library just by glancing through the source code.}

Answer 1

Option map method signature:

def map[B](f: (A) ⇒ B): Option[B]

And 'lift' method need to be defined as:

def lift[A,C,F[A] <: {def map[B <: C](f : A => B):F[B]}] (a : F[A])(g : A => C)
  = a map g

And call:

lift(Option(1)){ _ + 1 }
res: Option[Int] = Some(2)