Haskell n-ary tree traversal

Question

Sono abbastanza nuovo per Haskell e sto cercando di capire come attraversare un albero n-ary. Come uscita Sto cercando di ottenere un elenco di valori Leaf (come i rami non hanno alcun valore), quindi per testtree questo sarebbe: 4,5

La mia definizione finora è:

data Tree a = Leaf a | Branch [Tree a] deriving (Show) 

travTree     :: Tree a -> [a] 
travTree (Leaf x)   = [x] 
travTree (Branch (x:xs)) = travTree x : travTree xs 

testtree = Branch [(Leaf "4"), (Leaf "5")] 

Ma dà l'errore:

Couldn't match expected type `Tree a' 
    against inferred type `[Tree a]' 
In the first argument of `travTree', namely `xs' 
In the second argument of `(:)', namely `travTree xs' 
In the expression: travTree x : travTree xs 

sto assumendo questo è dovuto al xs essere un elenco di alberi e la sua attesa di un albero singolare. C'è un modo per fare questo? Ho provato la funzione di carta, seguendo le linee di:

travTree (Branch (x:xs)) = travTree x : map travTree xs 

Ma lamenta poi di:

Occurs check: cannot construct the infinite type: a = [a] 
When generalising the type(s) for `travTree' 

Ho anche provato a cambiare la firma funzione:

travTree     :: Tree a -> [b] 

che dà l'errore:

Couldn't match expected type `a' against inferred type `[b]' 
    `a' is a rigid type variable bound by 
     the type signature for `travTree' at Main.hs:149:36 
In the first argument of `(:)', namely `travTree x' 
In the expression: travTree x : map travTree xs 
In the definition of `travTree': 
    travTree (Branch (x : xs)) = travTree x : map travTree xs 

Qualsiasi aiuto sarebbe molto apprezzato, quindi grazie in anticipo ..!

Answer 1

Attraversare un albero significa attraversare tutti i sottoalberi e appiattire gli elenchi risultanti in uno.

Questo si traduce in

travTree (Branch branches) = concat $ map travTree branches 

noti che ci sono ancora notazioni più concisi come branches >>= travTree o concatMap travTree branches per il lato destro di questa definizione, ma ritengo quello superiore per essere il più chiaro.

Edit: Reintrodurre la versione lista-di comprensione per ragioni di completezza:

travTree (Branch branches) = [ elem | br <- branches, elem <- travTree br ] 

Answer 2

Sei nella giusta direzione con map, ma dopo aver attraversato ogni sotto-albero che si desidera concat le liste risultanti insieme . Non è inoltre necessario interrompere il primo elemento dell'elenco con il modello (x:xs) quando si utilizza map. Mi piacerebbe scrivere questo come:

travTree (Branch xs) = concatMap travTree xs 

(Ma attenzione, non ho ancora testato, che però spesso trovo la mia "Tipo di una infinita = [a]" i problemi sono causati da un map in cui è necessario concatMap!.)

Answer 3

Quando ero nuovo a Haskell mi sono imbattuto molto nello stesso problema. Alla fine ho capito come risolvere il problema rallentando e osservando i tipi. (Ai tempi in cui ho scritto un sacco di schema, io invece rallentato e guardare molto semplici coppie di input/output. Lo faccio a volte in Haskell, ma non fino a quando ho guardato i tipi.)

travTree     :: Tree a -> [a] 
travTree (Leaf x)   = [x] 
travTree (Branch (x:xs)) = travTree x : travTree xs 

Il tuo tipo sembra giusto: Tree a -> [a] suona come "tutte le foglie" per me.

travTree (Leaf x) = [x] 

Questo caso converte correttamente un Tree a ad un [a].

travTree (Branch (x:xs)) = travTree x : travTree xs 

OK, l'input è sicuramente un Tree a. Se l'uscita deve essere [a], e il primo operatore è (:) :: a -> [a] -> [a], quindi abbiamo bisogno di travTree x :: a e travTree xs :: [a]. funziona?

Beh, non riesce per due motivi: in realtà, travTree x :: [a], e non è possibile effettuare un elenco su un altro elenco (è necessario (++) :: [a] -> [a] -> [a] per quello). E non puoi passare [Tree a] a travTree :: Tree a -> [a] - gli dai un elenco di alberi quando si aspetta un singolo albero.

È possibile risolvere il secondo problema utilizzando map: map travTree xs. Questo ha il tipo [Tree a] -> [[a]]. Fortunatamente, questo si inserisce ora la travTree x :, in modo che

(travTree x : map travTree xs) :: [[a]] 

Ora non resta che il problema che hai [[a]] invece di [a]. concat risolve questo problema appiattendo una volta, in modo da

travTree (Branch (x:xs)) = concat (travTree x : map travTree xs) :: [a] 

che corrisponde al previsto Tree a -> [a].

Le altre risposte hanno ragione nel dire che la destrutturazione è inutile qui, ma spero che vedere i tipi enunciati ti aiuti a capire come imitare l'inferenza del tipo nella tua testa. In questo modo puoi capire cosa non va per altri problemi simili.