¿Alguien puede explicar la función transversal en Haskell?

99

Estoy intentando asimilar la traversefunción de Data.Traversable. No puedo ver su sentido. Como vengo de un trasfondo imperativo, ¿alguien puede explicarme en términos de un bucle imperativo? Se agradecería mucho el pseudocódigo. Gracias.

Konan
fuente
1
El artículo The Essence of the Iterator Pattern podría ser útil ya que construye la noción de recorrido paso a paso. Sin embargo
Jackie

Respuestas:

121

traversees lo mismo que fmap, excepto que también le permite ejecutar efectos mientras reconstruye la estructura de datos.

Eche un vistazo al ejemplo de la Data.Traversabledocumentación.

 data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)

La Functorinstancia de Treesería:

instance Functor Tree where
  fmap f Empty        = Empty
  fmap f (Leaf x)     = Leaf (f x)
  fmap f (Node l k r) = Node (fmap f l) (f k) (fmap f r)

Reconstruye todo el árbol, aplicándose fa cada valor.

instance Traversable Tree where
    traverse f Empty        = pure Empty
    traverse f (Leaf x)     = Leaf <$> f x
    traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r

La Traversableinstancia es casi la misma, excepto que los constructores se llaman en estilo aplicativo. Esto significa que podemos tener efectos (secundarios) al reconstruir el árbol. Aplicativo es casi lo mismo que mónadas, excepto que los efectos no pueden depender de resultados previos. En este ejemplo, significa que no podría hacer algo diferente a la rama derecha de un nodo dependiendo de los resultados de reconstruir la rama izquierda, por ejemplo.

Por razones históricas, la Traversableclase también contiene una versión monádica de traversecalled mapM. Para todos los efectos mapMes lo mismo que traverse: existe como un método separado porque Applicativesolo más tarde se convirtió en una superclase de Monad.

Si implementara esto en un lenguaje impuro, fmapsería lo mismo que traverse, ya que no hay forma de prevenir los efectos secundarios. No puede implementarlo como un bucle, ya que debe atravesar su estructura de datos de forma recursiva. Aquí hay un pequeño ejemplo de cómo lo haría en Javascript:

Node.prototype.traverse = function (f) {
  return new Node(this.l.traverse(f), f(this.k), this.r.traverse(f));
}

Sin embargo, implementarlo de esta manera te limita a los efectos que permite el lenguaje. Si desea el no determinismo (que es la instancia de la lista de modelos aplicativos) y su lenguaje no lo tiene incorporado, no tiene suerte.

Sjoerd Visscher
fuente
11
¿Qué significa el término "efecto"?
missingfaktor
24
@missingfaktor: Significa la información estructural de a Functor, la parte que no es paramétrica. El valor del estado en State, falla en Maybey Either, el número de elementos en []y, por supuesto, los efectos secundarios externos arbitrarios en IO. No me importa como un término genérico (como las Monoidfunciones que usan "vacío" y "agregar", el concepto es más genérico de lo que sugiere el término al principio) pero es bastante común y sirve bastante bien.
CA McCann
@CA McCann: Entendido. ¡Gracias por responder!
missingfaktor
1
"Estoy bastante seguro de que se supone que no debes hacer esto [...]". Definitivamente no, sería tan desagradable como hacer que los efectos de apdependan de los resultados anteriores. En consecuencia, he reformulado ese comentario.
duplode
2
"Aplicativo es casi lo mismo que las mónadas, excepto que los efectos no pueden depender de resultados previos". ... muchas cosas encajaron en mi lugar con esta línea, ¡gracias!
agam
58

traverseconvierte las cosas dentro de a Traversableen Traversablecosas "dentro" de an Applicative, dada una función que hace Applicatives de las cosas.

Usemos Maybecomo Applicativey enumeremos como Traversable. Primero necesitamos la función de transformación:

half x = if even x then Just (x `div` 2) else Nothing

Entonces, si un número es par, obtenemos la mitad (dentro de a Just), de lo contrario obtenemos Nothing. Si todo va "bien", se verá así:

traverse half [2,4..10]
--Just [1,2,3,4,5]

Pero...

traverse half [1..10]
-- Nothing

La razón es que la <*>función se usa para construir el resultado, y cuando uno de los argumentos es Nothing, Nothingregresamos.

Otro ejemplo:

rep x = replicate x x

Esta función genera una lista de longitud xcon el contenido x, por ejemplo rep 3= [3,3,3]. ¿Cuál es el resultado traverse rep [1..3]?

Obtenemos los resultados parciales de [1], [2,2]y [3,3,3]usando rep. Ahora la semántica de las listas como Applicativeses "tomar todas las combinaciones", por ejemplo, (+) <$> [10,20] <*> [3,4]es [13,14,23,24].

"Todas las combinaciones" de [1]y [2,2]son dos tiempos [1,2]. Todas las combinaciones de dos tiempos [1,2]y [3,3,3]son seis tiempos [1,2,3]. Entonces tenemos:

traverse rep [1..3]
--[[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3]]
Landei
fuente
1
Tu resultado final me recuerda esto .
hugomg
3
@missingno: Sí, se perdieronfac n = length $ traverse rep [1..n]
Landei
1
En realidad, está debajo de "Programador de codificación de listas" (pero usando listas por comprensión). Ese sitio web es completo :)
hugomg
1
@missingno: Hm, no es exactamente lo mismo ... ambos se basan en el comportamiento del producto cartesiano de la mónada de la lista, pero el sitio solo usa dos a la vez, por lo que es más parecido a hacer liftA2 (,)que usar la forma más genérica traverse.
CA McCann
41

Creo que es más fácil de entender en términos de sequenceA, como traversese puede definir de la siguiente manera.

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse f = sequenceA . fmap f

sequenceA secuencia los elementos de una estructura de izquierda a derecha, devolviendo una estructura con la misma forma que contiene los resultados.

sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
sequenceA = traverse id

También puede pensar sequenceAen invertir el orden de dos functores, por ejemplo, pasar de una lista de acciones a una acción que devuelve una lista de resultados.

Entonces, traversetoma algo de estructura y aplica fpara transformar cada elemento de la estructura en algún aplicativo, luego secuencia los efectos de esos aplicativos de izquierda a derecha, devolviendo una estructura con la misma forma que contiene los resultados.

También puedes compararlo con Foldable , que define la función relacionada traverse_.

traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()

Entonces puede ver que la diferencia clave entre Foldabley Traversablees que este último le permite preservar la forma de la estructura, mientras que el primero requiere que doble el resultado en algún otro valor.


Un ejemplo simple de su uso es usar una lista como estructura transitable, y IO como aplicativo:

λ> import Data.Traversable
λ> let qs = ["name", "quest", "favorite color"]
λ> traverse (\thing -> putStrLn ("What is your " ++ thing ++ "?") *> getLine) qs
What is your name?
Sir Lancelot
What is your quest?
to seek the holy grail
What is your favorite color?
blue
["Sir Lancelot","to seek the holy grail","blue"]

Si bien este ejemplo es bastante aburrido, las cosas se vuelven más interesantes cuando traversese usa en otros tipos de contenedores o con otros aplicativos.

Hammar
fuente
Entonces, ¿traverse es simplemente una forma más general de mapM? De hecho, sequenceA . fmappara listas es equivalente a sequence . map¿no?
Raskell
¿Qué quiere decir con "secuenciar efectos secundarios"? ¿Cuál es el 'efecto secundario' en su respuesta? Solo pensé que los efectos secundarios solo son posibles en las mónadas. Saludos.
Marek
1
@Marek "Solo pensé que los efectos secundarios son posibles solo en las mónadas" - La conexión es mucho más suelta que eso: (1) El IO tipo se puede usar para expresar efectos secundarios; (2) IOresulta ser una mónada, lo que resulta muy conveniente. Las mónadas no están esencialmente vinculadas a efectos secundarios. También debe tenerse en cuenta que existe un significado de "efecto" que es más amplio que "efecto secundario" en su sentido habitual, uno que incluye cálculos puros. Sobre este último punto, consulte también ¿Qué significa exactamente "eficaz" ?
duplode
(Por cierto, @hammar, me tomé la libertad de cambiar "efecto secundario" a "efecto" en esta respuesta debido a las razones descritas en el comentario anterior.)
duplode
17

Es algo así fmap, excepto que puede ejecutar efectos dentro de la función del mapeador, que también cambia el tipo de resultado.

Imagínese una lista de números enteros que representan los ID de usuario en una base de datos: [1, 2, 3]. Si desea que fmapestos ID de usuario sean nombres de usuario, no puede usar un tradicional fmap, porque dentro de la función debe acceder a la base de datos para leer los nombres de usuario (lo que requiere un efecto, en este caso, usar la IOmónada).

La firma de traversees:

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)

Con traverse, puede hacer efectos, por lo tanto, su código para asignar ID de usuario a nombres de usuario se ve así:

mapUserIDsToUsernames :: (Num -> IO String) -> [Num] -> IO [String]
mapUserIDsToUsernames fn ids = traverse fn ids

También hay una función llamada mapM:

mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)

Cualquier uso de mapMpuede ser reemplazado por traverse, pero no al revés. mapMsolo funciona para mónadas, mientras que traversees más genérico.

Si lo que desea es lograr un efecto y no devolver ningún valor útil, existen traverse_y mapM_versiones de estas funciones, los cuales ignoran el valor de retorno de la función y son un poco más rápido.

Kai Sellgren
fuente
7

traverse es el bucle. Su implementación depende de la estructura de datos a atravesar. Eso podría ser una lista, árbol, Maybe, Seq(influencia), o cualquier cosa que tenga una forma genérica de que se atraviesa a través de algo así como un ciclo for o función recursiva. Una matriz tendría un bucle for, una lista, un bucle while, un árbol o algo recursivo o la combinación de una pila con un bucle while; pero en los lenguajes funcionales no necesita estos engorrosos comandos de bucle: combina la parte interna del bucle (en forma de función) con la estructura de datos de una manera más directa y menos detallada.

Con la Traversableclase de tipos, probablemente podría escribir sus algoritmos de manera más independiente y versátil. Pero mi experiencia dice que por Traversablelo general solo se usa para simplemente pegar algoritmos a estructuras de datos existentes. Es bastante bueno no tener que escribir funciones similares para diferentes tipos de datos calificados también.

comonad
fuente