Kiselyov的拉链的惯用Scala翻译？

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的方法，并为每个案例类使用不同的实现。也很典型

在这里它是在行动：

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,24))

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

我如何计算shift，k和reset的类型，或者如何翻译TmapM？

我看着mapM，我知道这将允许我得到一个Cont，但是我不知道Cont内部是什么，因为它取决于shift。所以我开始转移。忽略haskell返回构造一个Cont，shift返回一个拉链。我也猜测，我需要添加一个类型A的元素到我的集合来构建。所以这个转移将在A型的元素所在的“孔”中，所以k将是A =>？功能。我们假设这个。在我不太清楚的类型之后，我提出了问号。所以我开始：

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

接下来我看(硬)在(k。也许一个id)。该函数可能是一个id将返回一个A，所以与k作为参数一致。它相当于a1.getOrElse(a)。另外因为我需要填写Z(a，？)，我需要弄清楚如何从选项到拉链获取一个函数。最简单的方法是假设k返回拉链。另外，看看如何使用拉链k1(无)或k1(Some(a))，我知道我必须为用户提供一种可选择替换元素的方式，这是正向函数所做的。它继续与原来的a或更新a。开始有意义所以现在我有：

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

接下来我再看一下mapM。我看到它是由回报组成的。 ZDone。忽略返回(因为它只是为Cont monad)，我看到ZDone将收集结果集。所以这是完美的，我只需要把它放在它，当程序到达那里，它将有更新的元素。此外，复位内的表达式的类型现在与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中继续monad的额外资源：

> http://blog.tmorris.net/continuation-monad-in-scala/
>当我第一次尝试时，我自己穿了什么：https://gist.github.com/huynhjl/4077185;它包括翻译到Scala各种Haskell继续示例以及Tiark的论文中的一些例子(但是不使用继承插件更清楚地指出了方法之间的相似性)。
>如果你下载scalaz，你可能可以让Tony Morris的cont一个scalaz Monad实例，并使用scalaz traverse – 然后翻译到scala将是一个更真实的。