[Haskell-cafe] Extracting all pruned sub trees
tomahawkins at gmail.com
Thu Jan 21 12:36:49 EST 2010
On Thu, Jan 21, 2010 at 4:07 PM, Mark Lentczner <markl at 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:
Very nice. Thanks!
More information about the Haskell-Cafe