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

Вы можете использовать плагин продолжения. После того, как плагин выполнит свои переводческие работы, он станет похож на монаду 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 для создания новых объектов или коллекций. Тип данных преобразуется в запечатанный типаж с расширением двух классов case. И я поместил функцию 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 возвращает Zipper. Я также предполагаю, что мне нужно добавить элемент типа A в мою коллекцию для сборки. Таким образом, сдвиг будет в «дыре», где ожидается элемент типа A, поэтому k будет A=>? функцией. Предположим это. Я ставлю вопросительные знаки после типов, в которых я не был так уверен. Итак, я начал с:

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

Затем я посмотрел (внимательно) на (k . maybe a id). Функция maybe a id вернет A, так что это согласуется с тем, что k принимает в качестве аргумента. Это эквивалент a1.getOrElse(a). Кроме того, поскольку мне нужно заполнить Z(a, ?), мне нужно выяснить, как получить функцию от option до Zipper. Самый простой способ - предположить, что k возвращает 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].

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

Мой перевод не такой общий или красивый, как перевод на 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 => B@cps[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, а также некоторых примеров из статьи Тиарка (но без использования плагина продолжения, который более четко указывает на сходство между подходами).
• если вы загрузите scalaz, вы сможете сделать Tony Morris cont экземпляром scalaz Monad и использовать scalaz traverse - тогда перевод на scala будет более буквальным.