Re: [Haskell-cafe] Extracting all pruned sub trees
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 aas = 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Extracting all pruned sub trees
On Thu, Jan 21, 2010 at 4:07 PM, Mark Lentczner ma...@glyphic.com 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Extracting all pruned sub trees
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. Something like this: data Leaf = ... data Tree = Leaf Leaf | Branch [Tree] prunedSubTrees :: Tree - [(Leaf, Tree)]-- [(the leaf removed, the pruned tree)] Any suggestions? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
