que - ¿Traducción idiomática de Scala de las cremalleras de Kiselyov?

que es una monada programacion funcional

Question

Oleg Kiselyov mostró cómo hacer una cremallera a partir de cualquier recorrido mediante el uso de continuaciones delimitadas. Su código Haskell es bastante corto:

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

Me he encontrado con algunos problemas al intentar implementarlo en Scala. Comencé a tratar de usar el paquete de continuaciones delimitado de Scala, pero incluso usando la idea richIterable de richIterable generalizada a @cps [X] en lugar de @suspendable, es imposible tener la función proporcionada para cambiar el retorno de un tipo diferente al de la función proporcionada para restablecer.

Intenté implementar la mónada de continuación siguiendo la definición de Kiselyov, pero Scala hace que sea difícil establecer parámetros de tipo y no pude averiguar cómo convertir Cont [R] en una mónada de una manera en que el método de desplazamiento de Scalaz estuviera contento.

Soy un principiante tanto en Haskell como en Scala, y realmente apreciaría la ayuda con esto.

Answer 1

Puedes usar el complemento de continuaciones. Después de que el plugin haga su trabajo de traducción, tiene similitudes con la mónada Cont y el shift y reset desde Oleg. La parte difícil es averiguar los tipos. Así que aquí está mi traducción:

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

El complemento de continuación es compatible con while loop pero no para map o flatMap , así que he elegido usar while y un ListBuffer mutable para capturar los elementos posiblemente actualizados. La función make_zipper se traduce en la aplicación complementaria Zipper.apply : una ubicación típica de Scala para crear nuevos objetos o colecciones. El tipo de datos se traduce en un rasgo sellado con dos clases de casos ampliados. Y he puesto la función zip_up como un método de Zipper con diferentes implementaciones para cada clase de caso. También es bastante típico.

Aquí está en acción:

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

¿Cómo T.mapM los tipos para shift , k y reset o cómo traducir T.mapM ?

mapM y sé que me permitirá obtener un Cont , pero no estoy seguro de qué hay dentro del Cont ya que depende del turno. Así que empiezo dentro del turno. Ignorando el return haskell para construir un Cont , shift devuelve un Zipper . También creo que necesito agregar un elemento de tipo A a mi colección para construir. Entonces, ¿el cambio estará en el "agujero" donde se espera un elemento de tipo A , por lo tanto, k será una A=>? función. Asumamos esto. Estoy poniendo signos de interrogación después de los tipos de los que no estaba tan seguro. Así que empecé con:

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

Luego miré (duro) a (k . maybe a id) . La función maybe a id devolverá una A , de modo que sea consistente con lo que k toma como argumento. Es el equivalente de a1.getOrElse(a) . También porque necesito rellenar Z(a, ?) , Necesito averiguar cómo obtener una función de la opción a la Cremallera. La forma más sencilla es asumir que k devuelve una Zipper . Además, observando cómo se usa la cremallera k1(None) o k1(Some(a)) , sé que tengo que dar una forma para que el usuario reemplace opcionalmente los elementos, que es lo que hace la función de forward . Continúa con el original o una actualización a . Empieza a tener sentido. Así que ahora tengo:

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

A continuación vuelvo a mirar mapM . Veo que está compuesto con return . ZDone return . ZDone . Ignorando el return nuevo (porque es solo para la mónada de Cont ), veo que ZDone tomará la colección resultante. Así que eso es perfecto, solo necesito coll y para cuando el programa llegue allí, tendrá los elementos actualizados. Además, el tipo de expresión dentro del reset ahora es consistente con el tipo de retorno de k que es Zipper[A] .

Finalmente, relleno el tipo de reinicio que el compilador puede inferir, pero cuando creo que es correcto, me da un (falso) sentido de confianza, sé lo que está pasando.

Mi traducción no es tan general ni tan bonita como la de Haskell porque no conserva el tipo de la colección y utiliza la mutación, pero espero que sea más fácil de entender.

Edición: aquí está la versión que conserva el tipo y usa una lista inmutable para que 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
    }
  }
}

Por cierto, aquí hay recursos adicionales sobre la mónada de continuación en scala:

• http://blog.tmorris.net/continuation-monad-in-scala/
• lo que me puse a prueba cuando lo probé por primera vez: https://gist.github.com/huynhjl/4077185 ; incluye traducir a Scala varios ejemplos de continuación de Haskell, así como algunos ejemplos del artículo de Tiark (pero sin usar el complemento de continuación, que señala más claramente la similitud entre el enfoque).
• Si descarga Scalaz, puede hacer que Tony Morris cont en una instancia de Scalaz Monad y usar Scalaz traverse , entonces la traducción a Scala sería más literal.