¿Es posible implementar liftM2 en Scala?

haskell monads

Question

En Haskell, liftM2 se puede definir como:

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

Me gustaría traducir esto a Scala. Mi primer intento fue el siguiente:

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)

Esto falla en lo que creo que es la forma más obvia posible: "el valor flatMap no es un miembro del tipo de parámetro M [T1]". Correcto, no he indicado que M[_] sea ​​algún tipo de mónada. Así que lo siguiente que intenté fue definir algún tipo estructural como:

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

... y tener M[A] <: Monad[A] . Pero eso no funciona, porque Scala no tiene tipos estructurales recursivos.

Así que las siguientes cosas que probé involucraron giros similares a M[A] <: FilterMonadic[A, _] . Todos fallaron, probablemente porque no pude averiguar el correcto-implícito-fu para CanBuildFrom .

La pregunta más relacionada que pude encontrar aquí en StackOverflow fue esta , tocando los tipos estructurales recursivos y cómo imitar las clases de tipos de Haskell en Scala. Pero ese enfoque requiere la definición de una conversión implícita de cada tipo que le importa al rasgo que define la clase de tipos, lo que parece terriblemente circular en este caso ...

¿Hay alguna buena manera de hacer lo que estoy tratando de hacer?

Answer 1

La forma habitual de codificar las clases de tipos en Scala es seguir de cerca a Haskell: List no implementa una interfaz de Monad (como es de esperar en un lenguaje orientado a objetos), sino que definimos la instancia de clase de tipo en un objeto separado. .

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
}

Esta idea se introduce en las Clases de tipo de los pobres y se explora más a fondo en Clases de tipo como objetos e implícitos . Tenga en cuenta que el método de point no podría haberse definido en una interfaz orientada a objetos, ya que no tiene M[A] como uno de sus argumentos para convertir a this referencia en una codificación OO. (O dicho de otra manera: no puede ser parte de una interfaz por la misma razón por la que una firma de constructor no puede representarse en una interfaz).

A continuación, puede escribir liftM2 como:

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)

Este patrón se ha aplicado extensivamente en Scalaz . La versión 7 , actualmente en desarrollo, incluye un índice de las clases de tipos .

Además de proporcionar clases de tipo e instancias para los tipos de biblioteca estándar, proporciona una capa ''sintáctica'' que permite el estilo más familiar de invocación del método de Receiver (Args) . Esto a menudo permite una mejor inferencia de tipo (teniendo en cuenta el algoritmo de inferencia de izquierda a derecha de Scala), y permite el uso del azúcar sintáctico de comprensión. A continuación, lo usamos para volver a escribir liftM2 , según los métodos de map y flatMap en 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)

Actualizar

Sí, es posible escribir una versión menos genérica de liftM2 para las colecciones de Scala. Solo tienes que CanBuildFrom todas las instancias de CanBuildFrom requeridas.

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)