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 for multi-parameter traversal
23 -- * Mapping combinators with an additional list
30 -- * Mapping combinators for twin traversal
36 -- * Typical twin traversals
43 ------------------------------------------------------------------------------
48 import Data.Generics.Basics
49 import Data.Generics.Aliases
51 ------------------------------------------------------------------------------
54 ------------------------------------------------------------------------------
56 -- The idiom for multi-parameter traversal
58 ------------------------------------------------------------------------------
62 gfoldl and friends so far facilitated traversal of a single term. We
63 will now consider an idiom gfoldlWith to traverse two terms
64 semi-simultaneously. By cascasding this idiom, we can also traverse
65 more than two terms. The gfoldlWith primitive completes gfoldl in a
66 way that is similar to the well-known couple map and
67 zipWith. Basically, gfoldlWith takes an additional argument, namely a
68 list, and this list is traversed simultaneously with the immediate
69 subterms of a given term.
74 -- | gfoldl with an additional list
76 => (forall a b. Data a => d -> c (a -> b) -> a -> c b)
77 -> (forall g. g -> c g)
82 gzipWith k z l x = case gfoldl k' z' x of { WITH _ c -> c }
84 k' (WITH (h:t) c) y = WITH t (k h c y)
85 k' (WITH [] _) _ = error "gzipWith"
89 -- | A type constructor for folding over the extra list
90 data WITH q c a = WITH [q] (c a)
94 ------------------------------------------------------------------------------
96 -- Mapping combinators with an additional list
98 ------------------------------------------------------------------------------
101 -- | gmapT with an additional list
103 => (forall a. Data a => b -> a -> a)
108 gzipWithT f l = unID . gzipWith k ID l
110 k b (ID c) x = ID $ c $ f b x
113 -- | gmapM with an additional list
114 gzipWithM :: (Data a, Monad m)
115 => (forall a. Data a => b -> a -> m a)
120 gzipWithM f = gzipWith k return
127 -- | gmapQl with an additional list
131 -> (forall a. Data a => b -> a -> r)
136 gzipWithQl o r f l = unCONST . gzipWith k z l
138 k b (CONST c) x = CONST (c `o` f b x)
142 -- | gmapQr with an additional list
146 -> (forall a. Data a => b -> a -> r')
151 gzipWithQr o r f l x = unQr (gzipWith k z l x) r
153 k b (Qr c) x = Qr (\r -> c (f b x `o` r))
157 -- | gmapQ with an additional list
159 => (forall a. Data a => b -> a -> u)
164 gzipWithQ f = gzipWithQr (:) [] f
168 ------------------------------------------------------------------------------
170 -- Helper type constructors
172 ------------------------------------------------------------------------------
176 -- | The identity type constructor needed for the definition of gzipWithT
177 newtype ID x = ID { unID :: x }
180 -- | The constant type constructor needed for the definition of gzipWithQl
181 newtype CONST c a = CONST { unCONST :: c }
184 -- | The type constructor needed for the definition of gzipWithQr
185 newtype Qr r a = Qr { unQr :: r -> r }
189 ------------------------------------------------------------------------------
191 -- Mapping combinators for twin traversal
193 ------------------------------------------------------------------------------
196 -- | Twin map for transformation
197 tmapT :: GenericQ (GenericT) -> GenericQ (GenericT)
199 gzipWithT unGenericT'
200 (gmapQ (\x -> GenericT' (f x)) x)
204 -- | Twin map for monadic transformation
205 tmapM :: Monad m => GenericQ (GenericM m) -> GenericQ (GenericM m)
207 gzipWithM unGenericM'
208 (gmapQ (\x -> GenericM' (f x)) x)
212 -- | Twin map for monadic transformation
213 tmapQ :: GenericQ (GenericQ r) -> GenericQ (GenericQ [r])
215 gzipWithQ unGenericQ'
216 (gmapQ (\x -> GenericQ' (f x)) x)
221 ------------------------------------------------------------------------------
223 -- Typical twin traversals
225 ------------------------------------------------------------------------------
227 -- | Generic equality: an alternative to \"deriving Eq\"
228 geq :: Data a => a -> a -> Bool
232 Testing for equality of two terms goes like this. Firstly, we
233 establish the equality of the two top-level datatype
234 constructors. Secondly, we use a twin gmap combinator, namely tgmapQ,
235 to compare the two lists of immediate subterms.
237 (Note for the experts: the type of the worker geq' is rather general
238 but precision is recovered via the restrictive type of the top-level
239 operation geq. The imprecision of geq' is caused by the type system's
240 unability to express the type equivalence for the corresponding
241 couples of immediate subterms from the two given input terms.)
247 geq' :: forall a b. (Data a, Data b) => a -> b -> Bool
248 geq' x y = and ( (toConstr x == toConstr y)
253 -- | Generic zip controlled by a function with type-specific branches
254 gzip :: (forall a b. (Data a, Data b) => a -> b -> Maybe b)
255 -> (forall a b. (Data a, Data b) => a -> b -> Maybe b)
258 -- See testsuite/.../Generics/gzip.hs for an illustration
262 if toConstr x == toConstr y
263 then tmapM (gzip f) x y