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

suma de dos numeros en haskell

Question

Estoy intentando y no Data.Traversable asimilar la función traverse 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.

Answer 1

Creo que es más fácil de entender en términos de sequenceA , ya que la traverse se 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 en sequenceA como invertir el orden de dos funtores, por ejemplo, pasar de una lista de acciones a una acción y devolver una lista de resultados.

Entonces, traverse toma cierta estructura, y 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 puede 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 Foldable y Traversable es que la última le permite conservar la forma de la estructura, mientras que la primera requiere que doble el resultado en algún otro valor.

Un ejemplo simple de su uso es usar una lista como la estructura atravesable e 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 vuelven más interesantes cuando se usa traverse en otros tipos de contenedores o usando otros aplicativos.

Answer 2

Es algo así como fmap , excepto que puedes 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 desea fmap estos ID de usuario a los nombres de usuario, no puede usar un fmap tradicional, 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 la mónada IO ) .

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 se puede reemplazar con traverse , pero no al revés. mapM solo funciona para mónadas, mientras que el traverse es más genérico.

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

Answer 3

traverse es el bucle. Su implementación depende de la estructura de datos a atravesar. Puede 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 una función for-loop o 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 la clase de tipo Traversable , probablemente podría escribir sus algoritmos de forma más independiente y versátil. Pero mi experiencia dice que Traversable generalmente solo se utiliza para pegar algoritmos a estructuras de datos existentes. Es bastante bueno no tener que escribir funciones similares para diferentes tipos de datos calificados, también.

Answer 4

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

Usemos Maybe Applicative y list 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 ), sino 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 la función <*> se usa para generar el resultado, y cuando uno de los argumentos es Nothing , obtenemos Nothing .

Otro ejemplo:

rep x = replicate x x

Esta función genera una lista de longitud x con el contenido x , por ejemplo, rep 3 = [3,3,3] . ¿Cuál es el resultado de la 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 Applicatives es "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 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]]

Answer 5

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 de la documentación de Data.Traversable .

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

La instancia de Functor 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

La instancia de Traversable 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, la clase Traversable también contiene una versión monádica de traverse llamada mapM . Para todos los propósitos y propósitos, mapM es lo mismo que traverse : existe como un método separado porque es solo aplicable recientemente debido a una superclase de Monad .

Si implementa esto en un lenguaje impuro, fmap sería lo mismo que traverse , ya que no hay forma de evitar 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 no desea el determinismo (que es la instancia de la lista de modelos Aplicativos) y su idioma no lo tiene incorporado, no tiene suerte.