Haskell n-ary tree traversal

Question

Soy bastante nuevo para Haskell y estoy tratando de averiguar cómo atravesar un árbol n-ario. Como salida Busco para obtener una lista de los valores de la hoja (como las ramas no tienen ningún valor), así que para testtree esto sería: 4,5

Mi definición hasta ahora es:

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

Pero se da el error:

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 

estoy suponiendo que esto se debe a xs es una lista de los árboles y su esperando un árbol singular. ¿Hay alguna forma de hacer esto? He estado tratando de la función de mapa, a lo largo de las líneas de:

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

Pero luego se queja de:

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

También he intentado cambiar la firma de función:

travTree     :: Tree a -> [b] 

que da el error:

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 

Cualquier ayuda sería muy apreciada, así que gracias de antemano ..!

Answer 1

Atravesar un árbol significa atravesar todos los subárboles y aplanar las listas resultantes en una sola.

Esto se traduce en

travTree (Branch branches) = concat $ map travTree branches 

Tenga en cuenta que incluso hay anotaciones más concisos como branches >>= travTree o concatMap travTree branches para el lado derecho de esta definición, pero considero que la de arriba para ser el más claro.

Editar: reintroducir la versión de la lista-comprensión en aras de la exhaustividad:

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

Answer 2

Usted está en la dirección correcta con map, pero después de atravesar cada subárbol que desee concat las listas resultantes juntos . Tampoco tiene sentido dividir el primer elemento de la lista con el patrón (x:xs) al usar map. Me gustaría escribir esto como:

travTree (Branch xs) = concatMap travTree xs 

(Pero cuidado, no he probado que sin embargo a menudo me encuentro a mi "tipo de una infinita = [a]" problemas son causados ​​por una map donde se necesita concatMap!.)

Answer 3

Cuando era nuevo en Haskell me encontré con el mismo problema mucho. Finalmente descubrí cómo resolver el problema disminuyendo la velocidad y mirando los tipos. (Antes, cuando escribí un montón de esquema, que en vez ralentizado y buscar en los pares de entrada/salida muy simples. Me hago a veces en Haskell, pero no hasta que he mirado los tipos.)

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

Su tipo se ve bien: Tree a -> [a] me suena a "todas las hojas".

travTree (Leaf x) = [x] 

Este caso se convierte correctamente un Tree a a un [a].

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

bien, la entrada es sin duda un Tree a. Si la salida debe ser [a], y el primer operador es (:) :: a -> [a] -> [a], entonces necesitamos travTree x :: a y travTree xs :: [a]. ¿Esto funciona?

Bueno, falla por dos razones: en realidad, travTree x :: [a], y no se puede contra una lista en otra lista (se necesita (++) :: [a] -> [a] -> [a] para eso). Y no puede pasar [Tree a] a travTree :: Tree a -> [a] - le está dando una lista de árboles cuando espera un solo árbol.

Puede solucionar el segundo problema utilizando map: map travTree xs. Esto tiene el tipo [Tree a] -> [[a]]. Afortunadamente, esto ahora se ajusta a la travTree x :, de manera que

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

Ahora sólo tiene el problema de que tiene [[a]] en lugar de [a]. concat resuelve este problema mediante el aplanamiento de una vez, así

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

que coincide con el Tree a -> [a] esperado.

Las otras respuestas están en lo cierto al decir que la desestructuración no tiene sentido aquí, pero espero que ver los tipos explicados te ayude a entender cómo imitar la inferencia de tipo en tu cabeza. De esa manera usted puede resolver lo que está mal para otros problemas similares.