Kiselyov拉链的惯用斯卡拉翻译？

Question

Oleg Kiselyov 展示了如何通过使用分隔的延续从任何可穿越的拉链制作拉链.他的Haskell代码非常简短:

module ZipperTraversable where 

import qualified Data.Traversable as T
import qualified Data.Map as M


-- In the variant Z a k, a is the current, focused value
-- evaluate (k Nothing) to move forward
-- evaluate (k v)       to replace the current value with v and move forward.

data Zipper t a = ZDone (t a) 
                | Z a (Maybe a -> Zipper t a)

make_zipper :: T.Traversable t => t a -> Zipper t a
make_zipper t = reset $ T.mapM f t >>= return . ZDone
 where
 f a = shift (\k -> return $ Z a (k . maybe a id))

-- The Cont monad for delimited continuations, implemented here to avoid
-- importing conflicting monad transformer libraries

newtype Cont r a = Cont{runCont :: (a -> r) -> r}

instance Monad (Cont r) where
    return x = Cont $ \k -> k x
    m >>= f  = Cont $ \k -> runCont m (\v -> runCont (f v) k)

-- Two delimited control operators,
-- without answer-type polymorphism or modification
-- These features are not needed for the application at hand

reset :: Cont r r -> r
reset m = runCont m id

shift :: ((a -> r) -> Cont r r) -> Cont r a
shift e = Cont (\k -> reset (e k))

我试图在Scala中实现它时遇到了一些问题.我开始试图使用Scala的分隔延续包,但即使使用Rompf的richIterable概念推广到@cps [X]而不是@suspendable,也不可能让提供的函数返回不同于提供给重置的函数的类型.

我尝试按照Kiselyov的定义实现continuation monad,但Scala使得很难对类型参数进行调整,而我无法弄清楚如何以scalaz的遍历方法满意的方式将Cont [R]转换为monad.

我是Haskell和Scala的初学者,非常感谢这方面的帮助.

Answer 1

您可以使用continuations插件.该插件不其翻译的作品后,有相似的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)
  }
}

continuations插件支持while循环,但不支持map或flatMap,所以我选择使用while和mutable 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,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构造a Cont,shift返回a Zipper.我还猜我需要A在我的集合中添加一个类型的元素来构建.因此,转移将在"洞"中,其中A期望一个类型的元素,因此k将是一个A=>?函数.我们假设这个.在我不太确定的类型之后我会加上问号.所以我开始:

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

接下来我看了(硬)(k . maybe a id).该函数maybe a id将返回一个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再次忽略(因为它只是为Contmonad),我看到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中continuation 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 遍历 - 那么对scala的翻译将更加文字化.