1 -----------------------------------------------------------------------------
3 -- Module : Data.Generics.Twins
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/>.
14 -----------------------------------------------------------------------------
16 module Data.Generics.Twins (
18 -- * The idiom of multi-parameter traversal
21 -- * Twin mapping combinators
26 -- * Prime examples of twin traversal
33 ------------------------------------------------------------------------------
36 import Data.Generics.Basics
37 import Data.Generics.Aliases
40 ------------------------------------------------------------------------------
43 ------------------------------------------------------------------------------
45 -- The idiom of multi-parameter traversal
47 ------------------------------------------------------------------------------
51 The fact that we traverse two terms semi-simultaneously is reflected
52 by the nested generic function type that occurs as the result type of
53 tfoldl. By "semi-simultaneously", we mean that we first fold over the
54 first term and compute a LIST of generic functions to be folded over
55 the second term. So the outermost generic function type is GenericQ
56 because we compute a list of generic functions which is a kind of
57 query. The inner generic function type is parameterised in a type
58 constructor c so that we can instantiate twin traversal for
59 transformations (T), queries (Q), and monadic transformations (M).
60 The combinator tfoldl is also parameterised by a nested generic
61 function which serves as the function to be mapped over the first term
62 to get the functions to be mapped over the second term. The combinator
63 tfoldl is further parameterised by gfoldl-like parameters k and z
64 which however need to be lifted to k' and z' such that plain term
65 traversal is combined with list traversal (of the list of generic
66 functions). That is, the essence of multi-parameter term traversal is
67 a single term traversal interleaved with a list fold. As the
68 definition of k' and z' details, the list fold can be arranged by the
69 ingredients of the term fold. To this end, we use a designated TWIN
70 datatype constructor which pairs a given type constructor c with a
71 list of generic functions.
75 tfoldl :: (forall a b. Data a => c (a -> b) -> c a -> c b)
76 -> (forall g. g -> c g)
77 -> GenericQ (Generic c)
78 -> GenericQ (Generic c)
80 tfoldl k z t xs ys = case gfoldl k' z' ys of { TWIN _ c -> c }
82 l = gmapQ (\x -> Generic' (t x)) xs
83 k' (TWIN (r:rs) c) y = TWIN rs (k c (unGeneric' r y))
87 -- Pairing ID, CONST, m or others with lists of generic functions
88 data TWIN c a = TWIN [Generic' c] (c a)
92 ------------------------------------------------------------------------------
94 -- Twin mapping combinators
96 ------------------------------------------------------------------------------
98 tmapT :: GenericQ (GenericT) -> GenericQ (GenericT)
99 tmapT f x y = unID $ tfoldl k z f' x y
102 k (ID c) (ID x) = ID (c x)
106 tmapQl :: (r -> r -> r)
108 -> GenericQ (GenericQ r)
109 -> GenericQ (GenericQ r)
110 tmapQl o r f x y = unCONST $ tfoldl k z f' x y
112 f' x y = CONST $ f x y
113 k (CONST c) (CONST x) = CONST (c `o` x)
117 tmapM :: Monad m => GenericQ (GenericM m) -> GenericQ (GenericM m)
118 tmapM f x y = tfoldl k z f x y
126 -- The identity type constructor needed for the definition of tmapT
127 newtype ID x = ID { unID :: x }
130 -- The constant type constructor needed for the definition of tmapQl
131 newtype CONST c a = CONST { unCONST :: c }
135 ------------------------------------------------------------------------------
137 -- Prime examples of twin traversal
139 ------------------------------------------------------------------------------
141 -- | Generic equality: an alternative to \"deriving Eq\"
142 geq :: Data a => a -> a -> Bool
146 Testing for equality of two terms goes like this. Firstly, we
147 establish the equality of the two top-level datatype
148 constructors. Secondly, we use a twin gmap combinator, namely tgmapQ,
149 to compare the two lists of immediate subterms.
151 (Note for the experts: the type of the worker geq' is rather general
152 but precision is recovered via the restrictive type of the top-level
153 operation geq. The imprecision of geq' is caused by the type system's
154 unability to express the type equivalence for the corresponding
155 couples of immediate subterms from the two given input terms.)
161 geq' :: forall a b. (Data a, Data b) => a -> b -> Bool
162 geq' x y = and [ (toConstr x == toConstr y)
163 , tmapQl (\b1 b2 -> and [b1,b2]) True geq' x y
167 -- | Generic zip controlled by a function with type-specific branches
168 gzip :: (forall a b. (Data a, Data b) => a -> b -> Maybe b)
169 -> (forall a b. (Data a, Data b) => a -> b -> Maybe b)
172 -- See testsuite/.../Generics/gzip.hs for an illustration
176 if toConstr x == toConstr y
177 then tmapM (gzip f) x y