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