Quelqu'un peut-il expliquer la fonction traverse en Haskell ?

Question

Je tente et échoue à comprendre la fonction traverse de Data.Traversable. Je ne parviens pas à en voir le but. Étant donné que je viens d'un background impératif, quelqu'un pourrait-il s'il vous plaît me l'expliquer en termes de boucle impérative? Un pseudo-code serait grandement apprécié. Merci.

Answer 1

traverser est identique à fmap, sauf qu'il vous permet également d'exécuter des effets pendant que vous reconstruisez la structure de données.

Jetez un œil à l'exemple de la documentation de Data.Traversable.

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

L'instance Functor de Tree serait :

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)

Il reconstruit tout l'arbre, en appliquant f à chaque valeur.

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

L'instance Traversable est presque la même, sauf que les constructeurs sont appelés dans un style applicatif. Cela signifie que nous pouvons avoir des effets (secondaires) tout en reconstruisant l'arbre. L'applicatif est presque le même que les monades, sauf que les effets ne peuvent pas dépendre des résultats précédents. Dans cet exemple, cela signifie que vous ne pourriez pas faire quelque chose de différent sur la branche droite d'un nœud en fonction des résultats de la reconstruction de la branche gauche par exemple.

Pour des raisons historiques, la classe Traversable contient également une version monadique de traverse appelée mapM. Pour toutes fins utiles, mapM est identique à traverse - il existe en tant que méthode distincte car Applicative est devenu plus tard une superclasse de Monad.

Si vous deviez implémenter ceci dans un langage impur, fmap serait identique à traverser, car il n'y a aucun moyen d'empêcher les effets secondaires. Vous ne pouvez pas l'implémenter comme une boucle, car vous devez traverser votre structure de données de manière récursive. Voici un petit exemple de la façon dont je le ferais en Javascript :

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

L'implémenter de cette manière vous limite aux effets que le langage permet cependant. Si vous voulez par exemple la non-déterminisme (que l'instance de liste de Applicative modélise) et que votre langage ne le supporte pas nativement, vous êtes malchanceux.

Answer 2

traverser transforme les choses à l'intérieur d'un Traversable en un Traversable de choses "à l'intérieur" d'un Applicative, en donnant une fonction qui crée des Applicative à partir de choses.

Utilisons Maybe comme Applicative et les listes comme Traversable. Tout d'abord, nous avons besoin de la fonction de transformation :

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

Donc si un nombre est pair, nous obtenons la moitié de celui-ci (à l'intérieur d'un Just), sinon nous obtenons Nothing. Si tout se passe "bien", cela ressemble à ceci :

traverser moitié [2,4..10]
--Just [1,2,3,4,5]

Mais...

traverser moitié [1..10]
-- Rien

La raison en est que la fonction <*> est utilisée pour construire le résultat, et lorsque l'un des arguments est Nothing, nous obtenons Nothing en retour.

Un autre exemple :

rep x = replicate x x

Cette fonction génère une liste de longueur x avec le contenu x, par exemple rep 3 = [3,3,3]. Quel est le résultat de traverser rep [1..3] ?

Nous obtenons les résultats partiels de [1], [2,2] et [3,3,3] en utilisant rep. Maintenant, la sémantique des listes en tant qu'Applicatives est "prendre toutes les combinaisons", par exemple (+) <$> [10,20] <*> [3,4] est [13,14,23,24].

"Toutes les combinaisons" de [1] et [2,2] sont deux fois [1,2]. Toutes les combinaisons de deux fois [1,2] et [3,3,3] sont six fois [1,2,3]. Ainsi nous avons :

traverser rep [1..3]
--[[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3]]

Answer 3

Je pense qu'il est plus facile de comprendre en termes de sequenceA, car traverse peut être défini comme suit.

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

sequenceA séquence les éléments d'une structure de gauche à droite, renvoyant une structure de même forme contenant les résultats.

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

Vous pouvez aussi penser à sequenceA comme inversant l'ordre de deux foncteurs, par exemple allant d'une liste d'actions à une action renvoyant une liste de résultats.

Ainsi, traverse prend une structure, et applique f pour transformer chaque élément de la structure en un applicatif, puis séquence les effets de ces applicatifs de gauche à droite, renvoyant une structure de même forme contenant les résultats.

Vous pouvez également le comparer à Foldable, qui définit la fonction associée traverse_.

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

Ainsi, vous pouvez voir que la principale différence entre Foldable et Traversable est que ce dernier vous permet de préserver la forme de la structure, tandis que le premier vous oblige à plier le résultat dans une autre valeur.

---

Un exemple simple de son utilisation est d'utiliser une liste comme structure traversable, et IO comme applicatif :

λ> 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"]

Alors que cet exemple est plutôt ennuyeux, les choses deviennent plus intéressantes lorsque traverse est utilisé sur d'autres types de conteneurs, ou en utilisant d'autres applicatifs.

Answer 4

C'est un peu comme fmap, sauf que vous pouvez exécuter des effets à l'intérieur de la fonction de mapping, ce qui change également le type de résultat.

Imaginez une liste d'entiers représentant des identifiants d'utilisateurs dans une base de données: [1, 2, 3]. Si vous voulez fmap ces identifiants d'utilisateurs en noms d'utilisateur, vous ne pouvez pas utiliser un fmap traditionnel, car à l'intérieur de la fonction vous devez accéder à la base de données pour lire les noms d'utilisateur (ce qui nécessite un effet -- dans ce cas, en utilisant le monade IO).

La signature de traverse est:

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

Avec traverse, vous pouvez effectuer des effets, donc votre code pour mapper les identifiants d'utilisateur en noms d'utilisateur ressemble à:

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

---

Il existe également une fonction appelée mapM:

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

Toute utilisation de mapM peut être remplacée par traverse, mais pas l'inverse. mapM ne fonctionne que pour les monades, alors que traverse est plus générique.

Si vous souhaitez simplement réaliser un effet et ne pas renvoyer de valeur utile, il existe des versions traverse_ et mapM_ de ces fonctions, qui ignorent la valeur de retour de la fonction et sont légèrement plus rapides.

Answer 5

traverser est la boucle. Son implémentation dépend de la structure de données à parcourir. Cela pourrait être une liste, un arbre, Peut-être, Séquence, ou tout ce qui a une façon générique d'être parcouru via quelque chose comme une boucle for ou une fonction récursive. Un tableau aurait une boucle for, une liste une boucle while, un arbre soit quelque chose de récursif ou la combinaison d'une pile avec une boucle while; mais dans les langages fonctionnels, vous n'avez pas besoin de ces commandes de boucle encombrantes: vous combinez la partie interne de la boucle (sous la forme d'une fonction) avec la structure de données d'une manière plus directe et moins verbeuse.

Avec la typeclasse Traversable, vous pourriez probablement écrire vos algorithmes de manière plus indépendante et polyvalente. Mais mon expérience dit que Traversable est généralement utilisé pour simplement coller des algorithmes à des structures de données existantes. Il est assez agréable de ne pas avoir à écrire des fonctions similaires pour différents types de données qualifiés, aussi.