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/>. The present module
13 -- provides support for multi-parameter traversal, which is also
14 -- demonstrated with generic operations like equality.
16 -----------------------------------------------------------------------------
18 module Data.Generics.Twins (
20 -- * The idiom of multi-parameter traversal
23 -- * Twin mapping combinators
28 -- * Prime examples of twin traversal
35 ------------------------------------------------------------------------------
38 import Data.Generics.Basics
39 import Data.Generics.Aliases
42 ------------------------------------------------------------------------------
45 ------------------------------------------------------------------------------
47 -- The idiom of multi-parameter traversal
49 ------------------------------------------------------------------------------
53 The fact that we traverse two terms semi-simultaneously is reflected
54 by the nested generic function type that occurs as the result type of
55 tfoldl. By "semi-simultaneously", we mean that we first fold over the
56 first term and compute a LIST of generic functions to be folded over
57 the second term. So the outermost generic function type is GenericQ
58 because we compute a list of generic functions which is a kind of
59 query. The inner generic function type is parameterised in a type
60 constructor c so that we can instantiate twin traversal for
61 transformations (T), queries (Q), and monadic transformations (M).
62 The combinator tfoldl is also parameterised by a nested generic
63 function which serves as the function to be mapped over the first term
64 to get the functions to be mapped over the second term. The combinator
65 tfoldl is further parameterised by gfoldl-like parameters k and z
66 which however need to be lifted to k' and z' such that plain term
67 traversal is combined with list traversal (of the list of generic
68 functions). That is, the essence of multi-parameter term traversal is
69 a single term traversal interleaved with a list fold. As the
70 definition of k' and z' details, the list fold can be arranged by the
71 ingredients of the term fold. To this end, we use a designated TWIN
72 datatype constructor which pairs a given type constructor c with a
73 list of generic functions.
77 tfoldl :: (forall a b. Data a => c (a -> b) -> c a -> c b)
78 -> (forall g. g -> c g)
79 -> GenericQ (Generic c)
80 -> GenericQ (Generic c)
82 tfoldl k z t xs ys = case gfoldl k' z' ys of { TWIN _ c -> c }
84 l = gmapQ (\x -> Generic' (t x)) xs
85 k' (TWIN (r:rs) c) y = TWIN rs (k c (unGeneric' r y))
89 -- Pairing ID, CONST, m or others with lists of generic functions
90 data TWIN c a = TWIN [Generic' c] (c a)
94 ------------------------------------------------------------------------------
96 -- Twin mapping combinators
98 ------------------------------------------------------------------------------
100 tmapT :: GenericQ (GenericT) -> GenericQ (GenericT)
101 tmapT f x y = unID $ tfoldl k z f' x y
104 k (ID c) (ID x) = ID (c x)
108 tmapQl :: (r -> r -> r)
110 -> GenericQ (GenericQ r)
111 -> GenericQ (GenericQ r)
112 tmapQl o r f x y = unCONST $ tfoldl k z f' x y
114 f' x y = CONST $ f x y
115 k (CONST c) (CONST x) = CONST (c `o` x)
119 tmapM :: Monad m => GenericQ (GenericM m) -> GenericQ (GenericM m)
120 tmapM f x y = tfoldl k z f x y
128 -- The identity type constructor needed for the definition of tmapT
129 newtype ID x = ID { unID :: x }
132 -- The constant type constructor needed for the definition of tmapQl
133 newtype CONST c a = CONST { unCONST :: c }
137 ------------------------------------------------------------------------------
139 -- Prime examples of twin traversal
141 ------------------------------------------------------------------------------
143 -- | Generic equality: an alternative to \"deriving Eq\"
144 geq :: Data a => a -> a -> Bool
148 Testing for equality of two terms goes like this. Firstly, we
149 establish the equality of the two top-level datatype
150 constructors. Secondly, we use a twin gmap combinator, namely tgmapQ,
151 to compare the two lists of immediate subterms.
153 (Note for the experts: the type of the worker geq' is rather general
154 but precision is recovered via the restrictive type of the top-level
155 operation geq. The imprecision of geq' is caused by the type system's
156 unability to express the type equivalence for the corresponding
157 couples of immediate subterms from the two given input terms.)
163 geq' :: forall a b. (Data a, Data b) => a -> b -> Bool
164 geq' x y = and [ (toConstr x == toConstr y)
165 , tmapQl (\b1 b2 -> and [b1,b2]) True geq' x y
169 -- | Generic zip controlled by a function with type-specific branches
170 gzip :: (forall a b. (Data a, Data b) => a -> b -> Maybe b)
171 -> (forall a b. (Data a, Data b) => a -> b -> Maybe b)
174 -- See testsuite/.../Generics/gzip.hs for an illustration
178 if toConstr x == toConstr y
179 then tmapM (gzip f) x y