[Haskell-cafe] Pruning the tree

Clive Brettingham-Moore haskell at brettingham-moore.net
Sun Jul 4 20:38:00 EDT 2004

> t =Leaf "1"
> treeGrower :: Tree String-> Tree String
> treeGrower (Leaf a )= treeGrower (Fork (Leaf (a++"1")) (Leaf (a++"2")))
> treeGrower (Fork l r)  = Fork (treeGrower l) (treeGrower r)
> data Tree a = Fork (Tree a) (Tree a) | Leaf a deriving Show
> inf=treeGrower t

Welcome to Haskell programming - you've hit your first bottom.

As a previous email noted, the type of tree grower could as well be
expressed as
treeGrower :: Tree String -> Tree a

This is because the tree is infinite (every time you generate tree with
leaves you apply treeGrower to it again), and as such has no reachable
leaves, only leaves contain typed data this tree cannot be typed.

While you could prune this tree to a given level, the leaves on the pruned
tree would not be from the grown tree (as they cannot be reached), but
generated by the pruning function. (It might make more sense if the forks
were labelled too, it depends on what you are trying to do).

> I'd like to prune it to a level to have a show of a piece
> like
> piece= prune 5 inf
> How prune is to be coded ??
> Thanks Paolino

Because no data is passed in the infinite tree I've added a base name to
the prune function (this is just off the top of my head no gurantees it
will run)

prune :: String -> Integer  -> Tree a -> Tree String
prune s 0 x = Leaf s -- make cut, pass name to generated leaf
prune s d (Leaf n) = Leaf n -- leave leaf, not necessary for infite tree
prune s d (Fork b1 b2) =
    Branch (prune (s++"R") (d-1) b1) (prune (s++"L") (d-1) b2)
-- last case does the work of generating labels

you might use:

prune "" 5 inf

Although it would be more direct to add a depth control to tree grower.


More information about the Haskell-Cafe mailing list