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


Estoy intentando y fracasando en asimilar traverse función de Data.Traversable. No puedo ver su punto. Como vengo de un trasfondo imperativo, ¿alguien puede explicarme en términos de un ciclo imperativo? Pseudocódigo sería muy apreciado. Gracias.


73
2017-09-18 10:09


origen


Respuestas:


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

Eche un vistazo al ejemplo del Data.Traversable documentación.

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

los Functor en vez de Tree serí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, aplicando f a 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

los Traversable la instancia es casi la misma, excepto que los constructores se llaman en estilo aplicativo. Esto significa que podemos tener efectos (laterales) 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 la reconstrucción de la rama izquierda, por ejemplo.

Por razones históricas, el Traversable clase también contiene una versión monádica de traverse llamado mapM. Para todos los efectos mapM es lo mismo que traverse - existe como un método separado porque Applicative solo más tarde se convirtió en una superclase de Monad.

Si implementa esto en un lenguaje impuro, fmap sería lo mismo que traverse, ya que no hay forma de prevenir los efectos secundarios. No puede implementarlo como un bucle, ya que tiene que atravesar su estructura de datos recursivamente. 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));
}

Implementarlo así te limita a los efectos que el lenguaje permite. Si f.e. quiere no determinismo (que la instancia de lista de modelos Aplicativos) y su lenguaje no lo tiene incorporado, no tiene suerte.


88
2017-09-18 11:18



traverse convierte las cosas dentro de una Traversable en un Traversable de cosas "dentro" Applicative, dada una función que hace Applicatives fuera de las cosas.

Vamos a usar Maybe como Applicative y lista 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 un Just), de lo contrario obtenemos Nothing. Si todo va "bien", se ve así:

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

Pero...

traverse half [1..10]
-- Nothing

La razón es que el <*> función se utiliza para generar el resultado, y cuando uno de los argumentos es Nothing, obtenemos Nothing espalda.

Otro ejemplo:

rep x = replicate x x

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

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

"Todas las combinaciones" de [1] y [2,2] son dos veces [1,2]. Todas las combinaciones de dos veces [1,2] y [3,3,3] son seis veces [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]]

46
2017-09-18 11:34



Creo que es más fácil de entender en términos de sequenceA, como traverse Puede ser definido como sigue

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

sequenceAsecuencia juntos 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 puedes pensar en sequenceA como invertir el orden de dos funtores, p. pasar de una lista de acciones a una acción y devolver una lista de resultados.

Asi que traverse toma algo de estructura y se aplica f para 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 Foldable, que define la función relacionada traverse_.

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

Entonces puedes ver que la diferencia clave entre Foldable y Traversable es que este último le permite conservar 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 la estructura atravesable, y IO como el 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 poco emocionante, las cosas se ponen más interesantes cuando traverse se usa en otros tipos de contenedores o usando otros aplicativos.


37
2017-09-18 10:19



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

Imagine una lista de enteros que representan ID de usuario en una base de datos: [1, 2, 3]. Si quieres fmap estas identificaciones de usuario a nombres de usuario, no puede usar una tradicional fmap, porque dentro de la función necesita acceder a la base de datos para leer los nombres de usuario (lo que requiere un efecto, en este caso, usar el IO monada).

La firma de traverse es:

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 mapear identificadores 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 mapM puede ser reemplazado por traverse, pero no al revés. mapM solo funciona para mónadas, mientras que traverse es más genérico

Si solo desea lograr un efecto y no devolver ningún valor útil, existen traverse_ y mapM_ versiones de estas funciones, que ignoran el valor de retorno de la función y son ligeramente más rápidas.


12
2017-11-06 18:23



traverse  es el lazo. Su implementación depende de la estructura de datos a atravesar. Eso podría ser una lista, árbol, Maybe, Seq(uence), o cualquier cosa que tenga una forma genérica de ser atravesada a través de algo así como un bucle forzado o función recursiva. Una matriz tendría un bucle for, una lista de while-loop, un árbol ya sea recursivo o la combinación de una pila con un while-loop; pero en los lenguajes funcionales no necesita estos complicados 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 el Traversable tipo de letra, probablemente podría escribir sus algoritmos de forma más independiente y versátil. Pero mi experiencia dice que Traversable usualmente solo se usa para pegar algoritmos a las estructuras de datos existentes. Es bastante bueno no tener que escribir funciones similares para diferentes tipos de datos calificados, también.


7
2017-09-29 02:12