Traduzione idiomatica di Scala delle cerniere di Kiselyov?

Question

Oleg Kiselyov showed how to make a zipper from any traversable utilizzando continuazioni delimitate. Il suo codice Haskell è piuttosto breve:

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

Ho incontrato qualche problema nel tentativo di implementarlo in Scala. Ho iniziato a provare a usare il pacchetto di continuazioni delimitato di Scala, ma anche usando l'idea di Rompf richIterable generalizzata a @cps [X] invece di @suspendable, è impossibile avere la funzione fornita per spostare il ritorno di un tipo diverso rispetto alla funzione fornita per resettare.

Ho provato ad implementare il monod di continuazione seguendo la definizione di Kiselyov, ma Scala rende difficile il curry dei parametri di tipo e non riesco a capire come trasformare Cont [R] in una monade in un modo che il metodo trasversale di scalaz fosse soddisfatto .

Sono un principiante sia ad Haskell che a Scala e apprezzerei molto l'aiuto con questo.

Answer 1

È possibile utilizzare il plug-in di continuazioni. Dopo che il plugin fa funzionare la sua traduzione, ha delle somiglianze con la monade Cont e la shift e la reset di Oleg. La parte difficile è capire i tipi. Così qui è la mia traduzione:

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) 
    } 
} 

Il plugin continuazioni ha il supporto per while ciclo, ma non per map o flatMap, così ho fatto la scelta di utilizzare while e mutabile ListBuffer per catturare gli elementi eventualmente aggiornati. La funzione make_zipper viene convertita nel compagno Zipper.apply - una tipica posizione Scala per la creazione di nuovi oggetti o raccolte. Il tipo di dati è tradotto in un tratto sigillato con due classi di casi estesi. E ho messo la funzione zip_up come un metodo di Zipper con diverse implementazioni per ogni classe di casi. Anche piuttosto tipico.

Qui è in azione:

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)) 
} 

Come ho fatto a capire i tipi per shift, k e reset o il modo di tradurre T.mapM?

Ho guardato mapM e so che mi consentirà di ottenere un Cont, ma non sono sicuro di cosa si trovi all'interno dello Cont in quanto dipende dal turno. Quindi inizio nel turno. Ignorando l'haskell return per creare un Cont, lo spostamento restituisce un Zipper. Immagino anche di dover aggiungere un elemento di tipo A alla mia raccolta da compilare. Quindi lo spostamento sarà nel "buco" in cui è previsto un elemento di tipo A, pertanto k sarà una funzione A=>?. Assumiamo questo. Metto dei punti interrogativi dopo i tipi di cui non ero tanto sicuro. Così ho iniziato con:

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

Poi ho guardato (duro) a (k . maybe a id). La funzione maybe a id restituirà un A, in modo coerente con ciò che assume k come argomento. È l'equivalente di a1.getOrElse(a). Anche perché ho bisogno di compilare Z(a, ?), ho bisogno di capire come ottenere una funzione da opzione a Zipper. Il modo più semplice è supporre che k restituisca uno Zipper.Inoltre, osservando come viene usata la cerniera k1(None) o k1(Some(a)), so che devo dare un modo per l'utente di sostituire facoltativamente gli elementi, che è ciò che fa la funzione forward. È continua con l'originale a o un a aggiornato. Inizia a dare un senso. Così ora ho:

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

Successivo guardo mapM di nuovo. Vedo che è composto con return . ZDone. Ignorando nuovamente return (perché è solo per la monade Cont), vedo che ZDone prenderà la raccolta risultante. Quindi è perfetto, ho solo bisogno di inserire coll al suo interno e nel momento in cui il programma arriva lì, avrà gli elementi aggiornati. Inoltre, il tipo dell'espressione all'interno di reset è ora coerente con il tipo restituito di k che corrisponde a Zipper[A].

Infine, inserisco il tipo di reset che il compilatore può dedurre, ma quando indovino giusto, mi dà un (falso) senso di sicurezza, so cosa sta succedendo.

La mia traduzione non è generale o carina come quella di Haskell perché non preserva il tipo dalla raccolta e utilizza la mutazione, ma si spera che sia più facile da capire.

Edit: Qui è la versione che conserva il tipo e utilizza una lista immutabile in modo che 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 
    } 
    } 
} 

---

A proposito, qui ci sono risorse aggiuntive sulla monade continuazione nella scala:

• http://blog.tmorris.net/continuation-monad-in-scala/
• cosa Mi sono messo in contatto quando ho provato per la prima volta: https://gist.github.com/huynhjl/4077185; include la traduzione in Scala di vari esempi di continuazione di Haskell e alcuni esempi tratti dal documento di Tiark (ma non l'uso del plugin di continuazione che indica più chiaramente la somiglianza tra l'approccio).
• se si scarica scalaz, si può essere in grado di creare un'istanza Monad scalaz di Tony Morris e utilizzare lo scalaz traverse - quindi la traduzione su scala sarebbe quindi più letterale.