Возможно ли реализовать liftM2 в Scala? - PullRequest
Новая
       32

Возможно ли реализовать liftM2 в Scala?

28 голосов
/ 03 декабря 2011

В Haskell liftM2 можно определить как: 

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

Я бы хотел перевести это на Скала. Моей первой попыткой было следующее: 

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)

Это терпит неудачу, как мне кажется, наиболее очевидным из возможных способов: «значение flatMap не является членом параметра типа M [T1]». Да, я не указал, что M[_] - это какая-то монада. Итак, следующее, что я попробовал, было определить некоторый структурный тип, такой как: 

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

... и иметь M[A] <: Monad[A]. Но это не работает, потому что у Scala нет рекурсивных структурных типов.

Итак, следующие несколько вещей, которые я попробовал, включали вращение, подобное M[A] <: FilterMonadic[A, _] Все они потерпели неудачу, вероятно потому, что я не смог выяснить правильное неявное-фу для CanBuildFrom.

Самым близким вопросом, который я мог найти здесь, в StackOverflow, был этот , касающийся как рекурсивных структурных типов, так и того, как имитировать классы типов Хаскелла в Scala. Но этот подход требует определения неявного преобразования каждого типа, который вас интересует, в черту, определяющую класс типов, которая в этом случае выглядит ужасно круглой ...

Есть ли какой-нибудь хороший способ сделать то, что я пытаюсь сделать?

1 Ответ

31 голосов
/ 03 декабря 2011

Обычный способ кодирования классов типов в Scala, как оказалось, очень близко следует за Haskell: List не реализует интерфейс Monad (как вы могли бы ожидать в объектно-ориентированном языке), но мы определяем введите экземпляр класса в отдельный объект. 

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
}

Эта идея представлена ​​в Классах типов бедных людей и более глубоко исследована в Классах типов как объектах и ​​последствиях . Обратите внимание, что метод point может , а не , был определен в объектно-ориентированном интерфейсе, так как он не имеет M[A] в качестве одного из аргументов для преобразования в ссылку this в ОО кодировка. (Или иначе: он не может быть частью интерфейса по той же причине, по которой сигнатура конструктора не может быть представлена ​​в интерфейсе.)

Затем вы можете написать liftM2 как: 

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)

Этот шаблон широко применяется в Scalaz . Версия 7 , находящаяся в настоящее время в разработке, включает в себя индекс классов типов .

В дополнение к предоставлению классов и экземпляров типов для стандартных типов библиотек, он предоставляет «синтаксический» слой, который позволяет более привычный стиль вызова метода receive.method (args) . Это часто обеспечивает лучший вывод типов (учитывая алгоритм вывода слева направо в Scala) и позволяет использовать синтаксический сахар для понимания. Ниже мы используем это для перезаписи liftM2 на основе методов map и flatMap в 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)

Обновление

Да, можно написать менее общую версию liftM2 для коллекций Scala. Вам просто нужно ввести все необходимые CanBuildFrom экземпляры. 

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)
...