Kiselyov拉鍊的習慣性斯卡拉翻譯？

Question

Oleg Kiselyov showed how to make a zipper from any traversable通過使用分隔延續。他的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，也不可能讓提供的函數返回與提供的重置函數不同的類型。

我嘗試了繼Kaneov的定義後繼續單子，但斯卡拉使它難以咖喱類型參數，我無法弄清楚如何將Cont [R]變成單子，以scalaz的遍歷方法滿意。

我是哈斯克爾和斯卡拉的初學者，非常感謝這方面的幫助。

Answer 1

您可以使用continuations插件。插件翻譯後，它與Oleg的Cont monad和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的方法，並針對每個案例類使用不同的實現。也很典型。

這是在行動：

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，班次返回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返回Zipper。另外，看看如何使用拉鍊​​或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 monad），我看到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 
    } 
    } 
} 

---

順便說一句，這裏有上階延續單子其他資源：

• http://blog.tmorris.net/continuation-monad-in-scala/
• 什麼當我第一次嘗試時，我把自己解決了：https://gist.github.com/huynhjl/4077185;它包括翻譯爲斯卡拉的各種Haskell延續示例以及來自Tiark論文的一些示例（但不使用延續插件，該插件更清楚地指出該方法之間的相似性）。
• 如果你下載scalaz，你或許​​可以讓Tony Morris繼續使用scalaz Monad實例並使用scalaz traverse - 那麼scala的翻譯將會是更真實的。