1{-# OPTIONS -fglasgow-exts #-}
2
3module Where (tests) where
4
5{-
6
7This example illustrates some differences between certain traversal
8schemes. To this end, we use a simple system of datatypes, and the
9running example shall be to replace "T1a 42" by "T1a 88". It is our
10intention to illustrate a few dimensions of designing traversals.
11
121. We can decide on whether we prefer "rewrite steps" (i.e.,
13monomorphic functions on data) that succeed either for all input
14patterns or only if the encounter a term pattern to be replaced. In
15the first case, the catch-all equation of such a function describes
16identity (see "stepid" below). In the second case, the catch-call
17equation describes failure using the Maybe type constructor (see
18"stepfail" below). As an intermediate assessment, the failure approach
19is more general because it allows one to observe if a rewrite step was
20meaningful or not. Often the identity approach is more convenient and
21sufficient.
22
232. We can now also decide on whether we want monadic or simple
24traversals; recall monadic generic functions GenericM from
25Data.Generics.  The monad can serve for success/failure, state,
26environment and others.  One can now subdivide monadic traversal
27schemes with respect to the question whether they simply support
28monadic style of whether they even interact with the relevant
29monad. The scheme "everywereM" from the library belongs to the first
30category while "somewhere" belongs to the second category as it uses
31the operation "mplus" of a monad with addition. So while "everywhereM"
32makes very well sense without a monad --- as demonstrated by
33"everywhere", the scheme "somewhere" is immediately monadic.
34
353. We can now also decide on whether we want rewrite steps to succeed
36for all possible subterms, at least for one subterm, exactly for one
37subterm, and others.  The various traversal schemes make different
38assumptions in this respect.
39
40a) everywhere
41
42   By its type, succeeds and requires non-failing rewrite steps.
43   However, we do not get any feedback on whether terms were actually
44   rewritten. (Say, we might have performed accidentally the identity
45   function on all nodes.)
46
47b) everywhereM
48
49   Attempts to reach all nodes where all the sub-traversals are performed
50   in monadic bind-sequence. Failure of the traversal for a given subterm
51   implies failure of the entire traversal. Hence, the argument of
52   "everywhereM" should be designed in a way that it tends to succeed
53   except for the purpose of propagating a proper error in the sense of
54   violating a pre-/post-condition. For example, "mkM stepfail" should
55   not be passed to "everywhereM" as it will fail for all but one term
56   pattern; see "recovered" for a way to massage "stepfail" accordingly.
57
58c) somewhere
59
60   Descends into term in a top-down manner, and stops in a given
61   branch when the argument succeeds for the subterm at hand. To this
62   end, it takes an argument that is perfectly intended to fail for
63   certain term patterns. Thanks to the employment of gmapF, the
64   traversal scheme recovers from failure when mapping over the immediate
65   subterms while insisting success for at least one subterm (say, branch).
66   This scheme is appropriate if you want to make sure that a given
67   rewrite step was actually used in a traversal. So failure of the
68   traversal would mean that the argument failed for all subterms.
69
70Contributed by Ralf Laemmel, ralf@cwi.nl
71
72-}
73
74import Test.Tasty.HUnit
75
76import Data.Generics
77import Control.Monad
78
79
80-- Two mutually recursive datatypes
81data T1 = T1a Int | T1b T2  deriving (Typeable, Data)
82data T2 = T2 T1             deriving (Typeable, Data)
83
84
85-- A rewrite step with identity as catch-all case
86stepid (T1a 42) = T1a 88
87stepid x        = x
88
89
90-- The same rewrite step but now with failure as catch-all case
91stepfail (T1a 42) = Just (T1a 88)
92stepfail _        = Nothing
93
94
95-- We can let recover potentially failing generic functions from failure;
96-- this is illustrated for a generic made from stepfail via mkM.
97recovered x = mkM stepfail x `mplus` Just x
98
99
100-- A test term that comprehends a redex
101term42 = T1b (T2 (T1a 42))
102
103
104-- A test term that does not comprehend a redex
105term37 = T1b (T2 (T1a 37))
106
107
108-- A number of traversals
109result1 = everywhere (mkT stepid)    term42   -- rewrites term accordingly
110result2 = everywhere (mkT stepid)    term37   -- preserves term without notice
111result3 = everywhereM (mkM stepfail) term42   -- fails in a harsh manner
112result4 = everywhereM (mkM stepfail) term37   -- fails rather early
113result5 = everywhereM recovered      term37   -- preserves term without notice
114result6 = somewhere (mkMp stepfail)  term42   -- rewrites term accordingly
115result7 = somewhere (mkMp stepfail)  term37   -- fails to notice lack of redex
116
117tests = gshow ( result1,
118              ( result2,
119              ( result3,
120              ( result4,
121              ( result5,
122              ( result6,
123              ( result7 ))))))) @=? output
124
125output = "((,) (T1b (T2 (T1a (88)))) ((,) (T1b (T2 (T1a (37)))) ((,) (Nothing) ((,) (Nothing) ((,) (Just (T1b (T2 (T1a (37))))) ((,) (Just (T1b (T2 (T1a (88))))) (Nothing)))))))"
126