{-# LANGUAGE DeriveDataTypeable #-} {-# LANGUAGE ScopedTypeVariables #-} {- A very, very simple example: "extract all Ints from a tree of Ints". The text book approach is to write a generalised fold for that. One can also turn the Tree datatype into functorial style and then write a Functor instance for the functorial datatype including a definition of fmap. (The original Tree datatype can be related to the functorial version by the usual injection and projection.) You can scrap all such boilerplate by using a traversal scheme based on gmap combinators as illustrated below. To get it a little more interesting, we use a datatype Tree with not just a case for leafs and fork trees, but we also add a case for trees with a weight. For completeness' sake, we mention that the fmap/generalised fold approach differs from the gmap approach in some details. Most notably, the gmap approach does not generally facilitate the identification of term components that relate to the type parameter of a parameterised datatype. The consequence of this is illustrated below as well. Sec. 6.3 in "Scrap Your Boilerplate ..." discusses such `type distinctions' as well. -} module FoldTree (tests) where import Test.HUnit -- Enable "ScrapYourBoilerplate" import Data.Generics -- A parameterised datatype for binary trees with data at the leafs data Tree a w = Leaf a | Fork (Tree a w) (Tree a w) | WithWeight (Tree a w) w deriving (Typeable, Data) -- A typical tree mytree :: Tree Int Int mytree = Fork (WithWeight (Leaf 42) 1) (WithWeight (Fork (Leaf 88) (Leaf 37)) 2) -- A less typical tree, used for testing everythingBut mytree' :: Tree Int Int mytree' = Fork (Leaf 42) (WithWeight (Fork (Leaf 88) (Leaf 37)) 2) -- Print everything like an Int in mytree -- In fact, we show two attempts: -- 1. print really just everything like an Int -- 2. print everything wrapped with Leaf -- So (1.) confuses leafs and weights whereas (2.) does not. -- Additionally we test everythingBut, stopping when we see a WithWeight node tests = show ( listify (\(_::Int) -> True) mytree , everything (++) ([] `mkQ` fromLeaf) mytree , everythingBut (++) (([],False) `mkQ` (\x -> (fromLeaf x, stop x))) mytree' ) ~=? output where fromLeaf :: Tree Int Int -> [Int] fromLeaf (Leaf x) = [x] fromLeaf _ = [] stop :: (Data a, Data b) => Tree a b -> Bool stop (WithWeight _ _) = True stop _ = False output = "([42,1,88,37,2],[42,88,37],[42])"