Tłumaczenie suwaków Kiselyova z Idiomatycznej Scali?

Question

Oleg Kiselyov showed how to make a zipper from any traversable za pomocą rozgraniczonych kontynuacji. Jego kod Haskella jest dość krótki:

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

Napotkałem kilka problemów, próbując go zaimplementować w Scali. Zacząłem próbować użyć zestawu rozgraniczeń kontynuowanych przez Scalę, ale nawet przy użyciu pomysłu Rompfa richIterable uogólnionego na @ cps [X] zamiast @suspendable, niemożliwe jest, aby funkcja dostarczona do przesunięcia zwróciła inny typ niż funkcja zapewniona do zresetowania.

Próbowałem implementować monadę kontynuacyjną zgodnie z definicją Kiselyova, ale Scala utrudnia stosowanie parametrów typu curry i nie mogłem wymyślić, jak zmienić Cont [R] w monadę w taki sposób, w jaki metoda trawersu skalaza była zadowolona z .

Jestem początkującym zarówno w Haskell i Scala, i naprawdę doceniam pomoc w tym.

Answer 1

Możesz użyć wtyczki kontynuacji. Po tym, jak wtyczka działa, jego podobieństwo do monady Cont i od shift i od Olega. Najtrudniejszą częścią jest ustalenie typów. Więc tutaj jest moje tłumaczenie:

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

Wtyczka kontynuacje posiada wsparcie dla while pętli, ale nie dla map lub flatMap, więc zrobiłem wybór za pomocą while i zmienny ListBuffer uchwycić możliwie aktualizowane elementy. Funkcja make_zipper jest tłumaczona na kompilator Zipper.apply - typową lokalizację Scala do tworzenia nowych obiektów lub kolekcji. Typ danych jest tłumaczony na zapieczętowaną cechę z rozszerzeniem o dwie klasy przypadków. I umieściłem funkcję zip_up jako metodę Zipper z różnymi implementacjami dla każdej klasy sprawy. Również dość typowy.

Oto ona w akcji:

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

Jak mogłem zorientować typy dla shift, k i reset lub jak tłumaczyć T.mapM?

Spojrzałem na mapM i wiem, że pozwoli mi uzyskać Cont, ale nie jestem pewien, co jest wewnątrz Cont, ponieważ zależy od zmiany. Więc zaczynam od wewnątrz zmiany. Zignorowanie haskell return w celu skonstruowania Cont, shift zwraca Zipper. Przypuszczam również, że muszę dodać element typu A do mojej kolekcji do kompilacji. Więc przesunięcie będzie w "dziurce", gdzie oczekiwany jest element typu A, dlatego k będzie funkcją A=>?. Załóżmy to. Wprowadzam znaki zapytania po typach, których nie byłem pewien. Zacząłem od:

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

Następnie wyglądałem (trudno) na (k . maybe a id). Funkcja maybe a id zwróci wartość A, co jest zgodne z tym, co k przyjmuje jako argument. Jest to odpowiednik a1.getOrElse(a). Również dlatego, że muszę wypełnić Z(a, ?), muszę dowiedzieć się, jak uzyskać funkcję od opcji do Zipper. Najprostszym sposobem jest założenie, że k zwraca Zipper.Również, patrząc na sposób użycia suwaka, k1(None) lub k1(Some(a)), wiem, że muszę dać użytkownikowi możliwość opcjonalnego zastąpienia elementów, co ma funkcja forward. It kontynuuje z oryginalnym a lub zaktualizowanym a. Zaczyna mieć sens. Teraz mam:

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

Następnie ponownie patrzę na mapM. Rozumiem, że składa się z return . ZDone. Ignorując ponownie return (ponieważ jest to tylko monada Cont), widzę, że ZDone przejmie wynikową kolekcję. Więc jest to idealne, po prostu muszę umieścić w nim coll i zanim program dotrze do niego, będzie miał zaktualizowane elementy. Również typ wyrażenia wewnątrz reset jest zgodny z typem zwracania k, który jest Zipper[A].

Na koniec wpisuję typ do resetowania, który kompilator może wywnioskować, ale kiedy się domyślam, daje mi (fałszywe) poczucie pewności, że wiem, co się dzieje.

Moje tłumaczenie nie jest tak ogólne ani tak piękne jak Haskella, ponieważ nie zachowuje tego typu z kolekcji i używa mutacji, ale mam nadzieję, że łatwiej ją zrozumieć.

Edit: Oto wersja, która zachowuje typ i wykorzystuje niezmienny listy tak, że 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 
    } 
    } 
} 

---

Przy okazji, tutaj są dodatkowe środki na monady kontynuacja w Scala:

• http://blog.tmorris.net/continuation-monad-in-scala/
• co Przeszedłem, kiedy pierwszy raz wypróbowałem: https://gist.github.com/huynhjl/4077185; obejmuje on tłumaczenie do Scali różnych przykładów kontynuacji Haskella, jak również przykład z pracy Tiarka (ale nie używanie wtyczki kontynuacyjnej, która wyraźniej wskazuje na podobieństwo podejścia).
• jeśli pobierzesz scalaz, możesz sprawić, by Tony Morris był kontrowersyjnym instancją Monada i używał skalazu traverse - wtedy tłumaczenie na scalę byłoby wtedy bardziej dosłownym.