Explicar la implementación de Traverse[List] en scalaz-seven

Question

Estoy tratando de entender el traverseImpl implementación en scalaz-siete:

def traverseImpl[F[_], A, B](l: List[A])(f: A => F[B])(implicit F: Applicative[F]) = {
  DList.fromList(l).foldr(F.point(List[B]())) {
     (a, fbs) => F.map2(f(a), fbs)(_ :: _)
  }
}

¿Alguien puede explicar cómo List interactúa con el Applicative?En última instancia, me gustaría poder implementar otras instancias para Traverse.

Answer 1

Un aplicativo le permite aplicar una función en un contexto a un valor en un contexto.Así, por ejemplo, puedes aplicar some((i: Int) => i + 1) a some(3) y obten some(4).Olvidémoslo por ahora.Volveré a eso más tarde.

La lista tiene dos representaciones, es Nil o head :: tail.Es posible que esté acostumbrado a doblarlo usando foldLeft pero hay otra manera de doblarlo:

def foldr[A, B](l: List[A], acc0: B, f: (A, B) => B): B = l match {
   case Nil => acc0
   case x :: xs => f(x, foldr(xs, acc0, f))
}

Dado List(1, 2) doblamos la lista aplicando la función comenzando desde el lado derecho, ¡aunque en realidad deconstruimos la lista desde el lado izquierdo!

f(1, f(2, Nil))

Esto se puede utilizar para calcular la longitud de una lista.Dado List(1, 2):

foldr(List(1, 2), 0, (i: Int, acc: Int) => 1 + acc)
// returns 2

Esto también se puede utilizar para crear otra lista:

foldr[Int, List[Int]](List(1, 2), List[Int](), _ :: _)
//List[Int] = List(1, 2)

Entonces, dada una lista vacía y el :: función pudimos crear otra lista.¿Qué pasa si nuestros elementos están en alguna contexto?Si nuestro contexto es aplicativo, aún podemos aplicar nuestros elementos y :: en ese contexto.Continuando con List(1, 2) y Option como nuestro aplicativo.Empezamos con some(List[Int]())) queremos aplicar el :: funcionar en el Option contexto.Esto es lo que el F.map2 hace.Se necesitan dos valores en su Option contexto, coloque la función proporcionada de dos argumentos en el Option contexto y aplicarlos juntos.

Así que fuera del contexto tenemos (2, Nil) => 2 :: Nil

En contexto tenemos: (Some(2), Some(Nil)) => Some(2 :: Nil)

Volviendo a la pregunta original:

// do a foldr 
DList.fromList(l).foldr(F.point(List[B]())) {
  // starting with an empty list in its applicative context F.point(List[B]())
  (a, fbs) => F.map2(f(a), fbs)(_ :: _)
  // Apply the `::` function to the two values in the context
}

No estoy seguro de por qué la diferencia DList se utiliza.Lo que veo es que usa trampolines, así que espero que esta implementación funcione sin arruinar la pila, pero no lo he probado, así que no lo sé.

La parte interesante de implementar el pliegue correcto como este es que creo que le brinda un enfoque para implementar el recorrido para tipos de datos algebricos usando catamorfismos.

Por ejemplo dado:

trait Tree[+A]
object Leaf extends Tree[Nothing]
case class Node[A](a: A, left: Tree[A], right: Tree[A]) extends Tree[A]

Fold se definiría así (que en realidad sigue el mismo enfoque que para List):

def fold[A, B](tree: Tree[A], valueForLeaf: B, functionForNode: (A, B, B) => B): B = {
  tree match {
    case Leaf => valueForLeaf
    case Node(a, left, right) => functionForNode(a, 
        fold(left, valueForLeaf, functionForNode), 
        fold(right, valueForLeaf, functionForNode)
      )
  }
}

Y Traverse usaría eso. fold con F.point(Leaf) y aplicarlo a Node.apply.Aunque no hay F.map3 por lo que puede resultar un poco engorroso.

Answer 2

Esto no es algo tan fácil de entender.Recomiendo leer el artículo enlazado al principio de mi blog sobre el tema.

También hice una presentación sobre el tema durante la última reunión de Programación Funcional en Sydney y pueden encontrar las diapositivas. aquí.

Si puedo intentar explicarlo en pocas palabras, traverse recorrerá cada elemento de la lista uno por uno y eventualmente reconstruirá la lista (_ :: _) pero acumulando/ejecutando algún tipo de "efectos" según lo dado por el F Applicative.Si F es State realiza un seguimiento de algún estado.Si F es el aplicativo correspondiente a un Monoid agrega algún tipo de medida para cada elemento de la lista.

La interacción principal de la lista y el aplicativo es con el map2 aplicación donde recibe un F[B] elemento y adjuntarlo al otro F[List[B]] elementos por definición de F como un Applicative y el uso de la List constructor :: como la función específica a aplicar.

A partir de ahí se ve que implementar otras instancias de Traverse se trata solo de applying los constructores de datos de la estructura de datos que desea atravesar.Si echas un vistazo a la presentación de PowerPoint vinculada, verás algunas diapositivas con un recorrido de árbol binario.

Answer 3

List#foldRight sopla la pila para listas grandes.Pruebe esto en un REPL:

List.range(0, 10000).foldRight(())((a, b) => ())

Normalmente, puede invertir la lista, utilizar foldLeft, luego invierta el resultado para evitar este problema.Pero con traverse Realmente tenemos que procesar los elementos en el orden correcto para asegurarnos de que el efecto se trate correctamente. DList Es una forma conveniente de hacerlo, mediante el trampolín.

Al final, estas pruebas deben pasar:

https://github.com/scalaz/scalaz/blob/scalaz-seven/tests/src/test/scala/scalaz/TraverseTest.scala#L13https://github.com/scalaz/scalaz/blob/scalaz-seven/tests/src/test/scala/scalaz/std/ListTest.scala#L11https://github.com/scalaz/scalaz/blob/scalaz-seven/core/src/main/scala/scalaz/Traverse.scala#L76