Is it possible to implement liftM2 in Scala?

Question

In Haskell, liftM2 can be defined as:

liftM2 :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r liftM2 f m1 m2 = do   x1 <- m1   x2 <- m2   return $ f x1 x2 

I'd like to translate this to Scala. My first attempt was the following:

def liftM2[T1, T2, R, M[_]](f: (T1, T2) => R)(ma: M[T1], mb: M[T2]) : M[R] = for {   a <- ma   b <- mb } yield f(a, b) 

This fails in what I guess is the most obvious way possible: "value flatMap is not a member of type parameter M[T1]". Right, I haven't indicated that M[_] is some kind of monad. So the next thing I tried was to define some structural type like:

type Monad[A] = {   def flatMap[B](f: (A) => Monad[B]): Monad[B] } 

... and to have M[A] <: Monad[A]. But that doesn't work, because Scala doesn't have recursive structural types.

So the next few things I tried involved gyrations similar to M[A] <: FilterMonadic[A, _]. Those all failed, probably because I wasn't able to figure out the right implicit-fu for CanBuildFrom.

The most closely-related question I could find here on StackOverflow was this one, touching both on recursive structural types and how to mimic Haskell's typeclasses in Scala. But that approach requires defining an implicit conversion from each type you care about to the trait defining the typeclass, which seems terribly circular in this case...

Is there any good way to do what I'm trying to do?

Answer 1

The usual way to encode type classes in Scala turns out to follow Haskell pretty closely: List doesn't implement a Monad interface (as you might expect in an object-oriented language), but rather we define the type class instance in a separate object.

trait Monad[M[_]] {    def point[A](a: => A): M[A]    def bind[A, B](ma: M[A])(f: A => M[B]): M[B]    def map[A, B](ma: M[A])(f: A => B): M[B] = bind(ma)(a => point(f(a))) }  implicit object listMonad extends Monad[List] {    def point[A](a: => A) = List(a)    def bind[A, B](ma: List[A])(f: A => List[B]) = ma flatMap f } 

This idea is introduced in Poor Man's Type Classes and explored more deeply in Type Classes as Objects and Implicits. Notice that the point method could not have been defined in an object-oriented interface, as it doesn't have M[A] as one of it's arguments to be converted to the this reference in an OO encoding. (Or put another way: it can't be part of an interface for the same reason a constructor signature can't be represented in an interface.)

You can then write liftM2 as:

def liftM2[M[_], A, B, C](f: (A, B) => C)                          (implicit M: Monad[M]): (M[A], M[B]) => M[C] =   (ma, mb) => M.bind(ma)(a => M.map(mb)(b => f(a, b)))  val f = liftM2[List, Int, Int, Int](_ + _)  f(List(1, 2, 3), List(4, 5)) // List(5, 6, 6, 7, 7, 8) 

This pattern has been applied extensively in Scalaz. Version 7, currently in development, includes an index of the type classes.

In addition to providing type classes and instances for standard library types, it provides a 'syntactic' layer that allows the more familiar receiver.method(args) style of method invocation. This often affords better type inference (accounting for Scala's left-to-right inference algorithm), and allows use of the for-comprehension syntactic sugar. Below, we use that to rewrite liftM2, based on the map and flatMap methods in MonadV.

// Before Scala 2.10 trait MonadV[M[_], A] {    def self: M[A]    implicit def M: Monad[M]     def flatMap[B](f: A => M[B]): M[B] = M.bind(self)(f)    def map[B](f: A => B): M[B] = M.map(self)(f) } implicit def ToMonadV[M[_], A](ma: M[A])                               (implicit M0: Monad[M]) =   new MonadV[M, A] {     val M = M0     val self = ma   }  // Or, as of Scala 2.10 implicit class MonadOps[M[_], A](self: M[A])(implicit M: Monad[M]) {   def flatMap[B](f: A => M[B]): M[B] = M.flatMap(self)(f)   def map[B](f: A => B): M[B] = M.map(self)(f) }   def liftM2[M[_]: Monad, A, B, C](f: (A, B) => C): (M[A], M[B]) => M[C] =   (ma, mb) => for {a <- ma; b <- mb} yield f(a, b) 

Update

Yep, its possible to write less generic version of liftM2 for the Scala collections. You just have to feed in all the required CanBuildFrom instances.

scala> def liftM2[CC[X] <: TraversableLike[X, CC[X]], A, B, C]      |           (f: (A, B) => C)      |           (implicit ba: CanBuildFrom[CC[A], C, CC[C]], bb: CanBuildFrom[CC[B], C, CC[C]])      |           : (CC[A], CC[B]) => CC[C] =      |   (ca, cb) => ca.flatMap(a => cb.map(b => f(a, b))) liftM2: [CC[X] <: scala.collection.TraversableLike[X,CC[X]], A, B, C](f: (A, B) => C)(implicit ba: scala.collection.generic.CanBuildFrom[CC[A],C,CC[C]], implicit bb: scala.collection.generic.CanBuildFrom[CC[B],C,CC[C]])(CC[A], CC[B]) => CC[C]  scala> liftM2[List, Int, Int, Int](_ + _) res0: (List[Int], List[Int]) => List[Int] = <function2>  scala> res0(List(1, 2, 3), List(4, 5)) res1: List[Int] = List(5, 6, 6, 7, 7, 8)