On Thu, Jan 21, 2010 at 4:07 PM, Mark Lentczner <[email protected]> wrote: > 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!
Very nice. Thanks! -Tom _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
