Идиоматический Scala перевод киселевских молний?

Ответ 1

Вы можете использовать плагин продолжения. После того, как плагин выполняет его перевод, он имеет сходство с монадой Cont и shift и reset от Олега. Трудная часть - выяснить типы. Итак, вот мой перевод:

import util.continuations._
import collection.mutable.ListBuffer

sealed trait Zipper[A] { def zipUp: Seq[A] }
case class ZDone[A](val zipUp: Seq[A]) extends Zipper[A]
case class Z[A](current: A, forward: Option[A] => Zipper[A]) extends Zipper[A] {
  def zipUp = forward(None).zipUp
}

object Zipper {
  def apply[A](seq: Seq[A]): Zipper[A] = reset[Zipper[A], Zipper[A]] {
    val coll = ListBuffer[A]()
    val iter = seq.iterator
    while (iter.hasNext) {
      val a = iter.next()
      coll += shift { (k: A=>Zipper[A]) =>
        Z(a, (a1: Option[A]) => k(a1.getOrElse(a)))
      }
    }
    ZDone(coll.toList)
  }
}

Плагин продолжения поддерживает цикл while, но не для map или flatMap, поэтому я сделал выбор с помощью while и изменяемого ListBuffer для захвата, возможно, обновленных элементов. Функция make_zipper преобразуется в компаньон Zipper.apply - типичное местоположение Scala для создания новых объектов или коллекции. Тип данных преобразуется в запечатанную черту с двумя расширениями классов. И я поставил zip_up-функцию как метод Zipper с различными реализациями для каждого класса case. Также довольно типичный.

Здесь он находится в действии:

object ZipperTest extends App {
  val sample = for (v <- 1 to 5) yield (v, (1 to v).reduceLeft(_ * _))
  println(sample) // Vector((1,1), (2,2), (3,6), (4,24), (5,120))

  def extract134[A](seq: Seq[A]) = {
    val Z(a1, k1) = Zipper(seq)
    val Z(a2, k2) = k1(None)
    val Z(a3, k3) = k2(None)
    val Z(a4, k4) = k3(None)
    List(a1, a3, a4)
  }
  println(extract134(sample)) // List((1,1), (3,6), (4,24))

  val updated34 = {
    val Z(a1, k1) = Zipper(sample)
    val Z(a2, k2) = k1(None)
    val Z(a3, k3) = k2(None)
    val Z(a4, k4) = k3(Some(42 -> 42))
    val z = k4(Some(88 -> 22))
    z.zipUp
  }
  println(updated34) // List((1,1), (2,2), (42,42), (88,22), (5,120))
}

Как я определил типы для shift, k и reset или как перевести T.mapM?

Я посмотрел на mapM, и я знаю, что это позволит мне получить Cont, но я не уверен, что находится внутри Cont, поскольку это зависит от сдвига. Поэтому я начинаю внутри смены. Игнорируя haskell return для построения Cont, shift возвращает a Zipper. Я также предполагаю, что мне нужно добавить элемент типа A в мою сборку для сборки. Таким образом, сдвиг будет в "дыре", где ожидается элемент типа A, поэтому k будет функцией A=>?. Предположим это. Я помещаю вопросительные знаки после тех типов, о которых я не был так уверен. Поэтому я начал с:

shift { (k: A?=>?) =>
  Z(a, ?)
}

Затем я посмотрел (тяжело) на (k . maybe a id). Функция maybe a id вернет a A, так что это соответствует тому, что k принимает как аргумент. Это эквивалентно a1.getOrElse(a). Кроме того, поскольку мне нужно заполнить Z(a, ?), мне нужно выяснить, как получить функцию из опции на Zipper. Самый простой способ - предположить, что k возвращает a Zipper. Кроме того, глядя, как используется молния k1(None) или k1(Some(a)), я знаю, что я должен предоставить пользователю возможность необязательно заменять элементы, что и делает функция forward. Он продолжается с оригинальным A или обновленным A. Это начинает иметь смысл. Итак, теперь у меня есть:

shift { (k: A=>Zipper[A]) =>
  Z(a, (a1: Option[A]) => k(a1.getOrElse(a)))
}

Далее я снова смотрю mapM. Я вижу, что он составлен с помощью return . ZDone. Игнорируя return снова (потому что это только для монады Cont), я вижу, что ZDone возьмет полученную коллекцию. Так что это идеально, мне просто нужно положить coll в него, и к тому моменту, когда программа поступит туда, у него будут обновленные элементы. Кроме того, тип выражения внутри reset теперь согласуется с типом возврата k, который равен Zipper[A].

Наконец, я заполняю тип для reset, который может сделать компилятор, но когда я предполагаю, что это правильно, это дает мне (ложное) чувство уверенности. Я знаю, что происходит.

Мой перевод не такой общий или симпатичный, как Haskell, потому что он не сохраняет тип из коллекции и использует мутацию, но, надеюсь, его легче понять.

Изменить: Вот версия, которая сохраняет этот тип и использует неизменяемый список, чтобы z.zipUp == z.zipUp:

import util.continuations._
import collection.generic.CanBuild
import collection.SeqLike

sealed trait Zipper[A, Repr] { def zipUp: Repr }
case class ZDone[A, Repr](val zipUp: Repr) extends Zipper[A, Repr]
case class Z[A, Repr](current: A,
    forward: Option[A] => Zipper[A, Repr]) extends Zipper[A, Repr] {
  def zipUp = forward(None).zipUp
}

object Zipper {
  def apply[A, Repr](seq: SeqLike[A, Repr])
                    (implicit cb: CanBuild[A, Repr]): Zipper[A, Repr] = {
    type ZAR = Zipper[A, Repr]

    def traverse[B](s: Seq[A])(f: A => [email protected][ZAR]): List[B]@cps[ZAR] =
      if (s.isEmpty) List()
      else f(s.head) :: traverse(s.tail)(f)

    reset {
      val list = traverse(seq.toSeq)(a => shift { (k: A=>ZAR) =>
        Z(a, (a1: Option[A]) => k(a1.getOrElse(a)))
      })
      val builder = cb() ++= list
      ZDone(builder.result): ZAR
    }
  }
}

Кстати, вот дополнительные ресурсы на продолжении монады в scala:

• http://blog.tmorris.net/continuation-monad-in-scala/
• Я пробовал себя, когда впервые попробовал: https://gist.github.com/huynhjl/4077185; он включает перевод на Scala различные примеры продолжения Haskell, а также некоторый пример из статьи Тиарка (но не использование плагина продолжения, который более четко указывает на сходство между подходом).
• Если вы скачаете скалаз, вы можете сделать Tony Morris cont экземпляром экземпляра Monad и использовать scalaz traverse - тогда перевод до Scala будет более буквальным.