Finding the leaves of an inductively-defined tree

Question

So, I have a function of type:

genTree :: Node -> [Nodes]

Given a node, this function generates the set of children of that node in a tree. The function can be applied again to those children to generate their children, until it eventually generates a node with no children, i.e. a node for which genTree returns [].

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

Any advice?

Answer 1

Let's generalize it a bit:

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

Applying static argument transformation (http://hackage.haskell.org/trac/ghc/ticket/888), we get

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

Use it as

leaves genTree root

or if you really want it to work only with genTree, inline it into the definition:

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

which is morally equivalent to sth's second answer.

Answer 2

flatten node = node : concatMap flatten (genTree node)

Answer 3

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

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

You can also combine these two functions into one to directly generate just a list of leaves, if you prefer:

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

Answer 4

(not exactly an answer to the question, but related)

I like to represent trees of a as "ListT [] a". (ListT from the List package in hackage)

Then the answer for this question is just to use the function lastL.

"Monad m => ListT m a" is a monadic list containing "a"s, where trying to get the next list item (which may find out there is no such item) is a monadic action in "m".

A usage example for ListT - a program that reads numbers from the user until the user does not type a number and prints the sum of numbers after each input:

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

Where repeat, scanl and takeWhile are from Data.List.Class. They work both for regular lists and monadic lists.

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

If you are familiar with Python, python iterators/generators are "ListT IO"s.

When using [] instead of IO as the monad of the monadic list, the result is a tree. Why? Imagine a list where getting the next item is an action in the list monad - the list monad means there are several options, therefore there are several "next items", which makes it a tree.

You can construct monadic lists either with higher-order functions (like the example above), or with cons, or with a python-generator notation (with yield) using the GeneratorT monad transformer from the generator package in hackage.

Disclaimer: ListT and GeneratorT are in no way widely used. I wrote those and I am not aware of any other users except for myself. There are several of users of equivalent ListTs, such as the one from the Haskell wiki, NondetT, and others.