{-# OPTIONS -fglasgow-exts #-}
module GMapQAssoc (tests) where
{-
This example demonstrates the inadequacy of an apparently simpler
variation on gmapQ. To this end, let us first recall a few facts.
Firstly, function application (including constructor application) is
left-associative. This is the reason why we had preferred our generic
fold to be left-associative too. (In "The Sketch Of a Polymorphic
Symphony" you can find a right-associative generic fold.) Secondly,
lists are right-associative. Because of these inverse associativities
queries for the synthesis of lists require some extra effort to
reflect the left-to-right of immediate subterms in the queried list.
In the module Data.Generics, we solve the problem by a common
higher-order trick, that is, we do not cons lists during folding but
we pass functions on lists starting from the identity function and
passing [] to the resulting function. The following example
illustrates that we get indeed an undesirable right-to-left order if
we just apply the simple constant datatype constructor CONST instead
of the higher-order trick.
Contributed by Ralf Laemmel, ralf@cwi.nl
-}
import Test.HUnit
import Data.Generics
-- The plain constant type constructor
newtype CONST x y = CONST x
unCONST (CONST x) = x
-- A variation on the gmapQ combinator using CONST and not Q
gmapQ' :: Data a => (forall a. Data a => a -> u) -> a -> [u]
gmapQ' f = unCONST . gfoldl f' z
where
f' r a = CONST (f a : unCONST r)
z = const (CONST [])
-- A trivial datatype used for this test case
data IntTree = Leaf Int | Fork IntTree IntTree
deriving (Typeable, Data)
-- Select int if faced with a leaf
leaf (Leaf i) = [i]
leaf _ = []
-- A test term
term = Fork (Leaf 1) (Leaf 2)
-- Process test term
-- gmapQ gives left-to-right order
-- gmapQ' gives right-to-left order
--
tests = show ( gmapQ ([] `mkQ` leaf) term
, gmapQ' ([] `mkQ` leaf) term
) ~=? output
output = show ([[1],[2]],[[2],[1]])