operazione di haskell fold sull'albero

Question

data Tree a = Tree a [Tree a] 

Si noti che non si accettano alberi vuoti e che una foglia è un albero con una lista vuota di sottoalberi.

treeFold :: (a -> [b] -> b) -> Tree a -> b 
treeFold f (Tree x s) = f x (map (treeFold f) s) 

Date le informazioni di cui sopra, non capisco come la funzione di piegatura albero restituisce un risultato applicando ricorsivamente l'operazione di piegatura per sottoalberi, quindi applicando la funzione all'etichetta alla radice ed i risultati restituito dai sottoalberi.

Inoltre non capisco come la funzione di piegatura albero richieda solo un argomento anziché 2, quando viene passato come argomento alla funzione mappa e continua a essere compilato e eseguito correttamente.

Ad esempio, la funzione di dimensione albero seguente, conta i nodi dell'albero.

treeSize :: Tree a -> Int 
treeSize = treeFold (\x ys -> 1 + sum ys) 

Quindi lanciando Treesize albero dove tree = Tree 4 [Tree 1 [Tree 2 [], Tree 3 []]] dà la dimensione dell'albero come 4.

Nella funzione dimensione albero sopra, la funzione di albero piega è anche passato un argomento invece di due. Inoltre, la x che viene passata alla funzione di piegatura dell'albero non viene utilizzata da nessuna parte, quindi perché ne hai bisogno lì. Rimuovendolo, il programma non viene compilato e viene visualizzato il seguente messaggio di errore.

Couldn't match type `a' with `[[Int] -> Int]' 
     `a' is a rigid type variable bound by 
      the type signature for treeSize :: Tree a -> Int 
      at treeFold.hs:15:1 
    In the first argument of `sum', namely `ys' 
    In the second argument of `(+)', namely `sum ys' 
    In the expression: 1 + sum ys 

Qualsiasi aiuto sarebbe molto apprezzato.

Answer 1

La prima domanda è un po 'complicata, perché questa è la cosa con ricorsione ... Come dicono gli insegnanti: "Per comprendere la ricorsione, devi imparare, come funziona la ricorsione". :-P Un piccolo consiglio: prova a passare attraverso l'applicazione di treeFold con un singolo albero o un albero con una sola albero all'interno e valuta il tuo (su un foglio o così). Penso, quindi potresti avere un'idea di cosa sta succedendo ... (ovviamente usa una semplice funzione come argomento per treeFold, come quello che usa treeSize).

treeFold ottiene un unico elemento a corpo cartina, perché map richiede una funzione da a->b, e treeFold ha il tipo (a -> [b] -> b) -> Tree a -> b., quindi se si desidera passare 2 argomenti si deve passare ad map solo un valore, che provoca una fallimento. (Un esempio comprensibile: (+) richiede due argomenti: se scrivi map (+1) [1,2,3] otterrai [2,3,4] , perché (+1) è applicato a ciascun elemento nell'elenco (e (+1) ha chiaramente bisogno di un altro argomento, come il vostro treeFold f sopra)

Il vostro esempio TreeSize:. non è giusto, quando si dice, che ottiene un solo argomento si potrebbe scrivere

treeSize t = treeFold (\x ys -> 1 + sum ys) t 

al posto del tuo definizione di cui sopra La x non è. usato perché per il conteggio è inutile.Ma, treeFoldn eeds per avere una funzione, che richiede due argomenti, quindi gli dai la x. Questa è l'unica ragione. Potresti passare qualsiasi altro valore.

Answer 2

Argomenti inutilizzati

primo luogo, il modo in cui si contrassegna esplicitamente una variabile come inutilizzata è quello di sostituire la variabile con _. Così si voleva davvero:

treeFold (\_ ys -> 1 + sum ys) 

hai un errore del compilatore, perché hai scritto:

treeFold (\ys -> 1 + sum ys) 

... che non è la stessa cosa.

Folds

In secondo luogo, io mano valutare treeSize su un albero di esempio, perché si può vedere che non c'è magia in corso:

treeSize (Tree 1 [Tree 2 [], Tree 3 []]) 

-- Inline definition of 'treeSize' 
= treeFold (\_ ys -> 1 + sum ys) (Tree 1 [Tree 2 [], Tree 3 []]) 

-- Evaluate treeFold 
= (\_ ys -> 1 + sum ys) 1 (map (treeFold (\_ ys -> 1 + sum ys)) [Tree 2 [], Tree 3 []]) 

-- Apply the anonymous function 
= 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) [Tree 2 [], Tree 3 []]) 

-- Apply the 'map' function 
= 1 + sum [ treeFold (\_ ys -> 1 + sum ys) (Tree 2 []) 
      , treeFold (\_ ys -> 1 + sum ys) (Tree 3 []) 
      ] 

-- Apply both 'treeFold' functions 
= 1 + sum [ (\_ ys -> 1 + sum ys) 2 (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      , (\_ ys -> 1 + sum ys) 3 (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      ] 

-- Apply the anonymous functions 
= 1 + sum [ 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      , 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      ] 

-- map f [] = [] 
= 1 + sum [ 1 + sum [] 
      , 1 + sum [] 
      ] 

-- sum [] = 0 
= 1 + sum [1 + 0, 1 + 0] 
= 1 + sum [1, 1] 

-- Apply 'sum' 
= 1 + 2 
= 3 

Tuttavia, c'è un modo semplice per ricordare come treeFold lavori. Tutto ciò sostituisce ogni costruttore Tree con la funzione con cui lo si fornisce.

Quindi, se si dispone di:

Tree 1 [Tree 2 [Tree 3 [], Tree 4[]], Tree 5 [Tree 6 [], Tree 7 []]] 

... e si applica treeFold f a ciò, valuterà a:

f 1 [f 2 [f 3 [], f 4 []], f 5 [f 6 [], f 7 []]] 

treeSum è solo il caso particolare in cui f = (\_ ys -> 1 + sum ys):

1 + sum [1 + sum [1 + sum [], 1 + sum []], 1 + sum [1 + sum [], 1 + sum []]] 

= 7 

Currying

Il punto finale è come funziona il curriculum in Haskell. Quando si definisce una funzione come:

foo x y = x + y 

... il compilatore in realtà desugars che a due funzioni nidificate:

foo = \x -> (\y -> x + y) 

Questo è il motivo per cui è possibile applicare funzioni parzialmente a un solo argomento a Haskell. Quando si scrive foo 1, si traduce in:

foo 1 

= (\x -> (\y -> x + y)) 1 

= \y -> 1 + y 

In altre parole, esso restituisce una nuova funzione di un argomento.

In Haskell, tutte le funzioni accettano esattamente un argomento e simuliamo le funzioni di più argomenti restituendo nuove funzioni. Questa tecnica è conosciuta come "currying".

Se si preferisce l'approccio multi-argomento più lingue tradizionali tradizionali, è possibile simulare avendo la funzione accetta un argomento tupla:

f (x, y) = x + y 

Tuttavia, questo non è proprio idiomatica Haskell, e ha vinto' Ti danno qualsiasi tipo di miglioramento delle prestazioni.