Qualcuno può spiegare la funzione traversa in Haskell

Question

Sono un principiante di Haskell. Sto provando e non riuscendo a liberare la funzione traverse dal modulo Data.Traversable. Non riesco a vedere il suo punto. Dal momento che provengo da un background imperativo, qualcuno può spiegarmelo in termini di un ciclo imperativo? Uno pseudo-codice sarebbe molto apprezzato. Grazie.

Answer 1

Penso che sia più facile da capire in termini di sequenceA, come traverse può essere definito come segue.

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

sequenceA sequenze insieme gli elementi di una struttura da sinistra a destra, restituendo una struttura con la stessa forma contenente i risultati.

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

Si può anche pensare sequenceA come invertire l'ordine delle due funtori, ad esempio passando da un elenco di azioni a un'azione che restituisce un elenco di risultati.

Così traverse richiede qualche struttura, e applica f di trasformare ogni elemento della struttura in qualche applicativa, poi sequenze fino gli effetti collaterali di tali applicativi da sinistra a destra, restituendo una struttura con la stessa forma contenente i risultati.

È inoltre possibile confrontarlo con Foldable, che definisce la funzione correlata traverse_.

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

Così si può vedere che la differenza fondamentale tra Foldable e Traversable è che quest'ultimo consente di mantenere la forma della struttura, mentre la prima richiede di piegare il risultato su in qualche altro valore.

---

Un semplice esempio del suo utilizzo sta usando una lista come la struttura attraversabile, e IO come applicativa:

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

Naturalmente, in questo caso è pari a mapM dal Preludio. Diventa più interessante se utilizzato su altri tipi di contenitori o utilizzando altri applicativi.

Answer 2

traverse è lo stesso di fmap, con la differenza che consente anche di eseguire effetti mentre si ricostruisce la struttura dati.

Dai un'occhiata all'esempio della documentazione Data.Traversable.

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

La Functor istanza di Tree sarebbe:

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) 

Si ricostruisce l'intero albero, applicando f ad ogni valore.

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 

Il Traversable esempio è quasi la stessa, tranne che i costruttori sono chiamati in stile applicativa. Ciò significa che possiamo avere effetti (laterali) durante la ricostruzione dell'albero.Applicativo è quasi la stessa cosa delle monadi, tranne che gli effetti non possono dipendere dai risultati precedenti. In questo esempio significa che non è possibile fare qualcosa di diverso dal ramo destro di un nodo, a seconda dei risultati della ricostruzione del ramo sinistro, ad esempio.

La classe Traversable contiene anche una versione monadica mapM dove gli effetti potrebbero, in linea di principio, dipendere dai risultati precedenti. (Anche se si sta sicuramente non dovresti farlo.) Ad esempio, fare l'effetto di f due volte se il ramo di sinistra è Empty:

mapM f (Node l k r) = do 
    l' <- mapM f l 
    k' <- case l' of 
    Empty -> do _ <- f k; f k 
    _  -> f k 
    r' <- mapM f r 
    return $ Node l' k' r' 

Se si implementa questo in una lingua impura, fmap e traverse sarebbe essere uguale a mapM, poiché non c'è modo di prevenire effetti collaterali. Non è possibile implementarlo come un ciclo, poiché è necessario attraversare ricorsivamente la struttura dei dati. Ecco un piccolo esempio di come lo farei in Javascript:

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

implementazione in questo modo si limita agli effetti che il linguaggio permette però. Se tu f.e. vuoi il non-determinismo (che l'istanza dell'elenco dei modelli Applicativi) e la tua lingua non lo hanno integrato, sei sfortunato.

Answer 3

traverse giri cose dentro un Traversable in una Traversable di cose "dentro" un Applicative, data una funzione che rende Applicative s di cose.

Usiamo Maybe come Applicative ed elenca come Traversable. In primo luogo abbiamo bisogno di funzione di trasformazione:

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

Quindi, se un numero è pari, otteniamo la metà di esso (all'interno di un Just), altrimenti otteniamo Nothing. Se tutto va "bene", sembra che questo:

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

Ma ...

traverse half [1..10] 
-- Nothing 

Il motivo è che la funzione <*> è usato per costruire il risultato, e quando uno degli argomenti è Nothing, otteniamo Nothing indietro.

altro esempio:

rep x = replicate x x 

Questa funzione genera un elenco di lunghezza x con il contenuto x, ad esempio rep 3 = [3,3,3]. Qual è il risultato di traverse rep [1..3]?

si ottengono i risultati parziali di [1], [2,2] e [3,3,3] utilizzando rep. Ora la semantica delle liste come Applicatives è "accetta tutte le combinazioni", ad es. (+) <$> [10,20] <*> [3,4] è [13,14,23,24].

"Tutte le combinazioni" di [1] e [2,2] sono due volte [1,2]. Tutte le combinazioni di due volte [1,2] e [3,3,3] sono sei volte [1,2,3].Così abbiamo:

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

Answer 4

traverseè il ciclo. La sua implementazione dipende dalla struttura dei dati da attraversare. Quello potrebbe essere un elenco, albero, forse, Seq (ence), o qualsiasi cosa che abbia un modo generico di essere attraversato via sth. come una funzione per il ciclo o ricorsiva. Un array avrebbe un ciclo for, un elenco un ciclo while, un albero o sth. ricorsivo o la combinazione di una pila con un ciclo while; ma nei linguaggi funzionali non hai bisogno di questi ingombranti comandi di loop: combinerai la parte interna del loop (nella forma di una funzione) con la struttura dei dati in modo più diretto e meno dettagliato.

Con il modello di classe Traversable, potresti probabilmente scrivere i tuoi algoritmi in modo più indipendente e versatile. Ma la mia esperienza dice che Traversable viene solitamente usato solo per incollare algoritmi a strutture esistenti. È abbastanza bello non aver bisogno di scrivere funzioni simili anche per diversi tipi di dati qualificati.

Answer 5

È un po 'come fmap, tranne che è possibile eseguire effetti collaterali all'interno della funzione mapper, che cambia anche il tipo di risultato.

Immaginate un elenco di numeri interi che rappresentano gli ID utente in un database: [1, 2, 3]. Se si desidera che questi ID utente siano fmap in nomi utente, non è possibile utilizzare un tradizionale fmap, perché all'interno della funzione è necessario accedere al database per leggere i nomi utente (che richiede un effetto collaterale - in questo caso, utilizzando la monade IO).

La firma di traverse è:

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

Con traverse, si può fare effetti collaterali, quindi, il codice per gli ID utente di mappatura di nomi utente si presenta come:

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

---

C'è anche una funzione denominata mapM:

mapM :: Monad m => (a -> m b) -> [a] -> m [b] 

Qualsiasi utilizzo di mapM può essere sostituito con traverse, ma non viceversa. mapM di solito funziona meglio di traverse, ma mapM funziona solo per le monadi con elenchi, mentre traverse è più generico.

Se si desidera ottenere un effetto collaterale e non restituire alcun valore utile, esistono le versioni traverse_ e mapM_ di queste funzioni, che ignorano entrambi il valore restituito dalla funzione e sono leggermente più veloci.