[email protected]
[Top] [All Lists]

Re: [Haskell-cafe] Extracting all pruned sub trees

Subject: Re: [Haskell-cafe] Extracting all pruned sub trees
From: Mark Lentczner
Date: Thu, 21 Jan 2010 07:07:46 -0800
On Jan 20, 2010, at 10:09 AM, Tom Hawkins wrote:
> I'm looking for an elegant way to generate a list of all pruned trees
> where each pruned tree has one of its leaves removed.

This turned out to be a thornier problem than I thought! (pun intended) 

> -- | A simple Tree type. 
> data Tree a = Leaf a | Branches [Tree a]
>       deriving Show
> 
> -- | Produce a list of all possible Trees that can result from pruning one 
> Leaf
> allPrunings :: Tree a -> [Tree a]
> allPrunings (Leaf _) = []
> allPrunings (Branches ts) = Branches `fmap` pruneInTurn ts
>     where pruneInTurn (a:as) = pruneOneWith a as ++ map (a:) (pruneInTurn as)
>           pruneInTurn _      = []
>           pruneOneWith (Leaf _) as = [ as ]
>           pruneOneWith a        as = map (:as) (allPrunings a)

The difficulty lies in the treatment of Branches vs Leaf: Pruning Branches 
laves a Tree who's head (well, "root") is of the same form, whereas pruning 
Leaf leaves nothing (no valid Tree). This gives rise for the need for the 
pruneOneWith function.

A more complete module with a small parser for a string tree language, and a 
nice, input and pring all prunings function can be found here:

        
http://bitbucket.org/mtnviewmark/haskell-playground/src/tip/cafe/TreePrune.hs

Enjoy!

        - Mark

Mark Lentczner
http://www.ozonehouse.com/mark/
IRC: mtnviewmark



_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe

<Prev in Thread] Current Thread [Next in Thread>