1 -----------------------------------------------------------------------------
3 -- Module : Data.Generics.Schemes
4 -- Copyright : (c) The University of Glasgow, CWI 2001--2003
5 -- License : BSD-style (see the file libraries/base/LICENSE)
7 -- Maintainer : libraries@haskell.org
8 -- Stability : experimental
9 -- Portability : non-portable
11 -- \"Scrap your boilerplate\" --- Generic programming in Haskell
12 -- See <http://www.cs.vu.nl/boilerplate/>. The present module provides
13 -- frequently used generic traversal schemes.
15 -----------------------------------------------------------------------------
17 module Data.Generics.Schemes (
31 ------------------------------------------------------------------------------
33 import Data.Generics.Basics
34 import Data.Generics.Aliases
39 -- | Apply a transformation everywhere in bottom-up manner
40 everywhere :: (forall a. Data a => a -> a)
41 -> (forall a. Data a => a -> a)
43 -- Use gmapT to recurse into immediate subterms;
44 -- recall: gmapT preserves the outermost constructor;
45 -- post-process recursively transformed result via f
47 everywhere f = f . gmapT (everywhere f)
50 -- | Apply a transformation everywhere in top-down manner
51 everywhere' :: (forall a. Data a => a -> a)
52 -> (forall a. Data a => a -> a)
54 -- Arguments of (.) are flipped compared to everywhere
55 everywhere' f = gmapT (everywhere' f) . f
58 -- | Variation on everywhere with an extra stop condition
59 everywhereBut :: GenericQ Bool -> GenericT -> GenericT
61 -- Guarded to let traversal cease if predicate q holds for x
64 | otherwise = f (gmapT (everywhereBut q f) x)
67 -- | Monadic variation on everywhere
68 everywhereM :: Monad m => GenericM m -> GenericM m
70 -- Bottom-up order is also reflected in order of do-actions
71 everywhereM f x = do x' <- gmapM (everywhereM f) x
75 -- | Apply a monadic transformation at least somewhere
76 somewhere :: MonadPlus m => GenericM m -> GenericM m
78 -- We try "f" in top-down manner, but descent into "x" when we fail
79 -- at the root of the term. The transformation fails if "f" fails
80 -- everywhere, say succeeds nowhere.
82 somewhere f x = f x `mplus` gmapMp (somewhere f) x
85 -- | Summarise all nodes in top-down, left-to-right order
86 everything :: (r -> r -> r) -> GenericQ r -> GenericQ r
88 -- Apply f to x to summarise top-level node;
89 -- use gmapQ to recurse into immediate subterms;
90 -- use ordinary foldl to reduce list of intermediate results
93 = foldl k (f x) (gmapQ (everything k f) x)
96 -- | Get a list of all entities that meet a predicate
97 listify :: Typeable r => (r -> Bool) -> GenericQ [r]
99 = everything (++) ([] `mkQ` (\x -> if p x then [x] else []))
102 -- | Look up a subterm by means of a maybe-typed filter
103 something :: GenericQ (Maybe u) -> GenericQ (Maybe u)
105 -- "something" can be defined in terms of "everything"
106 -- when a suitable "choice" operator is used for reduction
108 something = everything orElse
111 -- | Bottom-up synthesis of a data structure;
112 -- 1st argument z is the initial element for the synthesis;
113 -- 2nd argument o is for reduction of results from subterms;
114 -- 3rd argument f updates the sythesised data according to the given term
116 synthesize :: s -> (s -> s -> s) -> GenericQ (s -> s) -> GenericQ s
117 synthesize z o f x = f x (foldr o z (gmapQ (synthesize z o f) x))