Explicar Traverse aplicación [Lista] en scalaz y siete

Question

Estoy tratando de entender la aplicación traverseImpl en scalaz-seven:

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)(_ :: _) 
    } 
} 

¿Puede alguien explicar cómo el List interacciona 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. Entonces, por ejemplo, puede aplicar some((i: Int) => i + 1) a some(3) y obtener some(4). Olvidémoslo por ahora. Volveré a eso más tarde.

La lista tiene dos representaciones, es Nil o head :: tail. Que se puede utilizar para doblar sobre él, usando foldLeft Pero hay otra manera de doblar sobre ella:

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

Dada List(1, 2) plegamos sobre la lista de la aplicación de la función a partir del lado derecho - a pesar de que realmente deconstruir la lista del 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) 

Así da una lista vacía y la función :: hemos sido capaces de crear otra lista.¿Y si nuestros elementos están en algún contexto ? Si nuestro contexto es un aplicativo, entonces aún podemos aplicar nuestros elementos y :: en ese contexto. Continuando con List(1, 2) y Option como nuestro aplicativo. Comenzamos con some(List[Int]())) queremos aplicar la función :: en el contexto Option. Esto es lo que hace el F.map2. Toma dos valores en su contexto Option, coloque la función proporcionada de dos argumentos en el contexto Option y aplíquelos juntos.

Por lo tanto, fuera del contexto que tienen (2, Nil) => 2 :: Nil

En el 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é se utiliza la diferencia DList. Lo que veo es que usa trampolines, así que con suerte eso hace que esta implementación funcione sin arruinar la pila, pero no lo he intentado, así que no sé.

La parte interesante acerca de cómo implementar el doblez correcto de esta manera es que creo que le da un enfoque para implementar el poligonal para tipos de datos algebric usando catamorphisms.

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 como esta (que está realmente siguiendo 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 atravesar usaría ese fold con F.point(Leaf) y aplicarlo al Node.apply. Aunque no hay F.map3, puede ser un poco engorroso.

Answer 2

Esto no es algo tan fácil de entender. Recomiendo leer el artículo vinculado al comienzo de my blog post on the subject.

También hice una presentación sobre el tema durante la última reunión de programación funcional en Sydney y puede encontrar las diapositivas here.

Si puedo tratar de explicar en pocas palabras, traverse va a recorrer cada elemento de la lista uno por uno, con el tiempo volver a construir la lista (_ :: _) pero acumulando/ejecutar algún tipo de "efectos" como propuesta por el F Applicative. Si F es State, realiza un seguimiento de algún estado. Si F es el aplicativo correspondiente a Monoid, agrega algún tipo de medida para cada elemento de la lista.

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

Desde allí se ve que la implementación de otras instancias de Traverse es solo aproximadamente apply en los constructores de datos de la estructura de datos que desea recorrer. 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. Prueba esto en un REPL:

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

Por lo general, se puede revertir la lista, utilice foldLeft, luego revertir el resultado para evitar este problema. Pero con traverse tenemos que procesar los elementos en el orden correcto, para asegurarnos de que el efecto se trata correctamente. DList es una manera conveniente de hacer esto, en virtud de trampolín.

Al final, estas pruebas deben pasar:

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