Est-il possible de mettre en œuvre liftM2 en Scala?

Question

En Haskell, liftM2 peut être définie comme:

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

Je voudrais traduire cette à la Scala. Ma première tentative a été la suivante:

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)

Il échoue dans ce que je suppose est le moyen le plus évident possible: "la valeur flatMap n'est pas un membre de paramètre de type M[T1]". Bon, je n'ai pas indiqué qu' M[_] est une sorte de monade. Donc, la prochaine chose que j'ai essayé était de définir un certain type de structure comme:

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

... et pour avoir M[A] <: Monad[A]. Mais cela ne fonctionne pas, parce que la Scala n'a pas récursive types de construction.

Donc les prochaines choses que j'ai essayé impliqués fluctuations similaire M[A] <: FilterMonadic[A, _]. Ceux qui ont tous échoué, probablement parce que je n'étais pas en mesure de comprendre le droit implicite-fu pour CanBuildFrom.

Les plus étroitement liés à la question que j'ai pu trouver ici sur StackOverflow a cette une, touchant à la fois sur récursive des types structuraux et comment faire pour imiter Haskell typeclasses en Scala. Mais cette approche nécessite de définir une conversion implicite de chaque type de soins sur le trait de la définition de la typeclass, qui semble terriblement circulaire dans ce cas...

Est-il un bon moyen de faire ce que je suis en train de faire?

Answer 1

La façon habituelle de coder les classes de type de Scala s'avère à suivre Haskell à peu de choses près: List ne pas mettre en œuvre un Monad interface (comme vous pouvez vous attendre dans un langage orienté-objet), mais plutôt de définir le type de l'instance de classe dans un objet séparé.

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
}

Cette idée est introduite dans du Pauvre Type Classes et exploré plus profondément dans les Classes de Type en tant qu'Objets et Implicites. Notez que l' point méthode pourrait ne pas avoir été définies dans une interface orientée objet, car il n'a pas M[A] comme l'un de ses arguments pour être converti en this référence dans un OO encodage. (Ou dans l'autre sens: il ne peut pas faire partie d'une interface pour la même raison, une signature du constructeur ne peut pas être représenté dans une interface.)

Vous pouvez ensuite écrire liftM2 comme:

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)

Ce modèle a été largement appliquées dans Scalaz. La Version 7, actuellement en développement, comprend un indice du type de classes.

En plus de fournir le type de classes et d'instances pour le standard de la bibliothèque de types, il procure un "syntaxique" couche qui permet les plus connues du récepteur.méthode(args) style de l'invocation de méthode. Souvent, cela permet de mieux l'inférence de type (de la comptabilité pour la Scala de gauche à droite algorithme d'inférence), et permet d'utiliser le pour-de la compréhension sucre syntaxique. Ci-dessous, nous utilisons que de réécrire liftM2, basée sur l' map et flatMap méthodes MonadV.

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
  }

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)

Mise à jour

Yep, il est possible d'écrire moins de la version générique de liftM2 pour la Scala de collections. Vous avez juste à se nourrir dans tous les CanBuildFrom des cas.

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)