Trouver les feuilles d'un arbre

Question

inductivement défini Donc, j'ai une fonction de type:

genTree :: Node -> [Nodes] 

Compte tenu d'un nœud, cette fonction génère l'ensemble des enfants de ce noeud dans un arbre. La fonction peut à nouveau être appliquée à ces enfants pour générer leurs enfants, jusqu'à ce qu'elle génère finalement un nœud sans enfants, c'est-à-dire un nœud pour lequel genTree renvoie []. Ce que j'essaye de faire est, donné un noeud de départ, de générer la liste de tous les noeuds de feuille dans l'arbre qui l'a comme racine.

Un conseil?

Answer 1

La fonction de la réponse de Martijn génère une liste de tous les nœuds dans l'arborescence. Vous pouvez utiliser cette liste et filtrer les nœuds sans enfants pour obtenir les feuilles:

nodes root = root : concatMap nodes (genTree root) 
leaves root = filter (null . genTree) (nodes root) 

Vous pouvez également combiner ces deux fonctions en un seul pour générer directement juste une liste de feuilles, si vous préférez:

leaves node 
    | null children = [node] 
    | otherwise  = concatMap leaves children 
    where children = genTree node 

Answer 2

Généralisons un peu:

leaves :: (a -> [a]) -> a -> [a] 
leaves tree x = case (tree x) of 
        [] -> [x] 
        -- the node x has no children and is therefore a leaf 
        xs -> concatMap (leaves tree) xs 
        -- otherwise get list of all leaves for each child and concatenate them 

Application transformation argument statique (http://hackage.haskell.org/trac/ghc/ticket/888), nous obtenons

leaves :: (a -> [a]) -> a -> [a] 
leaves tree x = leaves' x where 
    leaves' x = case (tree x) of 
       [] -> [x] 
       xs -> concatMap leaves' xs 

utiliser comme

leaves genTree root 

ou si vous vraiment veux que cela fonctionne seulement avec genTree, en ligne dans la définition:

leaves1 root = case (genTree x) of 
       [] -> [x] 
       xs -> concatMap leaves1 xs 

qui est moralement équivalent à la deuxième réponse de sth.

Answer 3

flatten node = node : concatMap flatten (genTree node) 

Answer 4

(pas exactement une réponse à la question, mais connexe)

J'aime représenter les arbres d'un comme « ListT [] a ». (ListT à partir du package List dans hackage)

Ensuite, la réponse à cette question est simplement d'utiliser la fonction lastL.

« Monad m => ListT m a » est une liste contenant monadique s « a de « où essayer d'obtenir l'élément suivant de la liste (qui peut savoir il n'y a pas un objet) est une action monadique dans » m ».

Un exemple d'utilisation pour ListT - un programme qui lit les chiffres de l'utilisateur jusqu'à ce que l'utilisateur ne tapez pas de numéro et imprime la somme des chiffres après chaque entrée:

main = 
    execute . joinM . fmap print . 
    scanl (+) 0 . 
    fmap (fst . head) . 
    takeWhile (not . null) . 
    fmap reads . 
    joinM $ (repeat getLine :: ListT IO (IO String)) 

Où repeat, scanl et takeWhile sont à partir de Data.List.Class. Ils travaillent à la fois pour les listes régulières et les listes monadiques.

joinM :: List l => l (ItemM l a) -> l a -- (l = ListT IO, ItemM l = IO) 
execute :: List l => l a -> ItemM l() -- consume the whole list and run its actions 

Si vous êtes familier avec Python, itérateurs/générateurs python sont "ListT IO" s.

Lorsque vous utilisez [] au lieu de IO comme monade de la liste monadique, le résultat est un arbre. Pourquoi? Imaginez une liste où obtenir l'élément suivant est une action dans la liste monad - la liste monad signifie qu'il y a plusieurs options, donc il y a plusieurs "éléments suivants", ce qui en fait un arbre.

On peut construire des listes monadique soit avec des fonctions d'ordre supérieur (comme l'exemple ci-dessus), ou avec cons, ou avec une notation python-générateur (avec yield) à l'aide du transformateur GeneratorT monade de l'emballage generator dans hackage.

Avertissement: ListT et GeneratorT ne sont pas largement utilisés. Je les ai écrits et je ne connais pas d'autres utilisateurs sauf moi-même. Il y a plusieurs utilisateurs de ListT équivalents, tels que celui du wiki Haskell, , et d'autres.