Marionetta, astrazione II°

La logica del movimento di un singolo pezzo deve servire a modificare tutta la struttura, ma non abbiamo sviluppato lo strumento per farlo.

Un buon esercizio per imparare a percorrere l’albero è implementare la sua istanza di funtore, che significa applicare una funzione data a tutti i contenuti dei suoi nodi.

Cerchiamo una funzione

funtoreAlbero :: (a -> b) -> Albero a -> Albero b

Anche le liste sono funtori attraverso

map :: (a -> b) -> [a] -> [b]

Per il datatype Albero si tratta di smontare un nodo, applicare la funzione (a -> b) al suo contenuto di tipo ‘a’ e applicare la stessa funzione a tutti i suoi sottonodi.

funtoreAlbero f (Albero x ys) = Albero (f x) $ map (funtoreAlbero f) ys

Controlliamo i tipi coinvolti


*Main> :t funtoreAlbero
funtoreAlbero :: (a -> b) -> Albero a -> Albero b
*Main> :t \f -> map (funtoreAlbero f)
\f -> map (funtoreAlbero f) :: (a -> b) -> [Albero a] -> [Albero b]
*Main>

La funzione funtoreAlbero è corretta come tipo.
Il secondo tipo richiesto ci introduce al concetto di astrazione lambda, ovvero funzioni anonime. Sono funzioni create lì per lì, e che quindi non desideriamo riutilizzare altrove.
La sintassi utilizza la coppia ‘\’ e ‘->’ . Dopo il simbolo ‘\’ (lambda) si introducono gli argomenti, dopo il simbolo ‘->’ la definizione della funzione.
In realtà questo è l’unico modo di scrivere le funzioni.

funzione x y z = blah blah

si traduce in

funzione = \x y z -> blah blah

Tornando alla richiesta, abbiamo chiesto il tipo di una funzione con argomento ‘f’ definita come “map (funtoreAlbero f)”. Il risultato ci dice che ‘f’ è di tipo (a -> b) , l’argomento della funzione “map (funtoreAlbero f)” sarà una lista di ‘Alberi a’ e produrrà una lista di ‘Alberi b’. Quindi esattamente quello che cercavamo per trasformare i sottonodi.

Vediamo come funziona

*Main> let x = Albero 0 [Albero 1 [Albero 2 [],Albero 3 []],Albero 4 []]
*Main> funtoreAlbero (\x -> x * 2) x
Albero 0 [Albero 2 [Albero 4 [],Albero 6 []],Albero 8 []]
*Main> 

La funzione passata è una lambda che moltiplica per 2 il suo argomento. L’albero ottenuto ha la stessa struttura dell’albero originale e i contenuti dei suoi nodi moltiplicati per 2.

*Main> funtoreAlbero even x
Albero True [Albero False [Albero True [],Albero False []],Albero True []]
*Main> funtoreAlbero (\y -> even y) x
Albero True [Albero False [Albero True [],Albero False []],Albero True []]

Qui la funzione produce valore vero se il suo argomento è pari. Notare che scrivere even è come scrivere \y -> even y. Questo tipo di semplificazione si chiama riduzione eta.

Il funtore è molto limitato, perché applica la stessa funzione a tutti i nodi. Se volessimo applicare una funzione con parametri diversi in ogni nodo, non riusciremmo a farlo.
Allora costruiamo un’altra HOF: zipAlberoWith.

zipAlberoWith :: (a -> b -> c) -> Albero a -> Albero b -> Albero c

La funzione che cerchiamo deve smontare gli alberi dati in parallelo e ricavare i due argomenti della funzione data per ricreare il nuovo nodo.

zipAlberoWith f (Albero x xs) (Albero y ys) = Albero (f x y) $ zipWith (zipAlberoWith f) xs ys

Per zippare le liste di sottonodi utilizziamo lo stesso concetto per le liste. zipWith è una funzione della libreria di base.

*Main> :t zipWith
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

Proviamo zipAlberoWith

*Main> let x = Albero 0 [Albero 1 [Albero 2 [],Albero 3 []],Albero 4 []]
*Main> let y = Albero 3 [Albero 4 [Albero 1 [],Albero 2 []],Albero 0 []]
*Main> zipAlberoWith (*) x y
Albero 0 [Albero 4 [Albero 2 [],Albero 6 []],Albero 0 []]

I nodi sono stati moltiplicati membro a membro.

Facciamo qualcosa con le semirette

*Main> let x = Albero 20 [Albero 15 [],Albero 30 [Albero 10 []], Albero 40 [Albero 5 []],Albero 50 [Albero 12 []], Albero (-10) [Albero (-30.0) []]]
*Main> zipAlberoWith (\(Semiretta p t) r -> Semiretta p (t + r)) marionetta x
Albero (Semiretta (Punto (0.0,50.0)) 290.0) 
  [ Albero (Semiretta (Punto (0.0,60.0)) 105.0) []
  , Albero (Semiretta (Punto (15.0,45.0)) 330.0) [Albero (Semiretta (Punto (45.0,-5.0)) (-25.0)) []]
  , Albero (Semiretta (Punto (-15.0,45.0)) 340.0) [Albero (Semiretta (Punto (-45.0,-5.0)) (-30.0)) []]
  , Albero (Semiretta (Punto (10.0,-30.0)) 350.0) [Albero (Semiretta (Punto (40.0,-85.0)) 282.0) []]
  , Albero (Semiretta (Punto (-10.0,-30.0)) 290.0) [Albero (Semiretta (Punto (-40.0,-85.0)) 240.0) []]
  ]

Abbiamo aggiunto alle semirette della marionetta un angolo diverso a seconda del nodo. Notare che ‘x’ ha la stessa forma di ‘marionetta’, definito nell’articolo pre-precedente.

Bene, siamo quasi in fondo.

Annunci

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...