Search for leaves of an inductively defined tree

Question

So, I have a function like:

genTree :: Node -> [Nodes]

Given node, this function generates a set of children of this node in the tree. The function can again be applied to these children to generate its children until it eventually creates a node without children, i.e. A node for which genTree returns [].

What I'm trying to do, given the starting node, will generate a list of all leaf nodes in the tree that has it as the root.

Any tips?

Answer 1

The Martijn response function generates a list of all nodes in the tree. You can use this list and filter out nodes without children to get leaves:

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

, , :

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

Answer 2

:

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

(http://hackage.haskell.org/trac/ghc/ticket/888),

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

leaves genTree root

, genTree, :

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

.

Answer 3

( , )

a "ListT [] a". (ListT List )

- lastL.

"Monad m => ListT m a" , "a" s, ( , ) "m".

ListT - , , :

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

repeat, scanl takeWhile Data.List.Class. , .

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

Python, / python "ListT IO" s.

[] IO . ? , - - , , " ", .

(, ), cons, - ( yield) GeneratorT monad generator .

: ListT GeneratorT . , , . ListT s, Haskell wiki, NondetT .

Answer 4

flatten node = node : concatMap flatten (genTree node)