{-# OPTIONS -fglasgow-exts #-} module Where (tests) where {- This example illustrates some differences between certain traversal schemes. To this end, we use a simple system of datatypes, and the running example shall be to replace "T1a 42" by "T1a 88". It is our intention to illustrate a few dimensions of designing traversals. 1. We can decide on whether we prefer "rewrite steps" (i.e., monomorphic functions on data) that succeed either for all input patterns or only if the encounter a term pattern to be replaced. In the first case, the catch-all equation of such a function describes identity (see "stepid" below). In the second case, the catch-call equation describes failure using the Maybe type constructor (see "stepfail" below). As an intermediate assessment, the failure approach is more general because it allows one to observe if a rewrite step was meaningful or not. Often the identity approach is more convenient and sufficient. 2. We can now also decide on whether we want monadic or simple traversals; recall monadic generic functions GenericM from Data.Generics. The monad can serve for success/failure, state, environment and others. One can now subdivide monadic traversal schemes with respect to the question whether they simply support monadic style of whether they even interact with the relevant monad. The scheme "everywereM" from the library belongs to the first category while "somewhere" belongs to the second category as it uses the operation "mplus" of a monad with addition. So while "everywhereM" makes very well sense without a monad --- as demonstrated by "everywhere", the scheme "somewhere" is immediately monadic. 3. We can now also decide on whether we want rewrite steps to succeed for all possible subterms, at least for one subterm, exactly for one subterm, and others. The various traversal schemes make different assumptions in this respect. a) everywhere By its type, succeeds and requires non-failing rewrite steps. However, we do not get any feedback on whether terms were actually rewritten. (Say, we might have performed accidentally the identity function on all nodes.) b) everywhereM Attempts to reach all nodes where all the sub-traversals are performed in monadic bind-sequence. Failure of the traversal for a given subterm implies failure of the entire traversal. Hence, the argument of "everywhereM" should be designed in a way that it tends to succeed except for the purpose of propagating a proper error in the sense of violating a pre-/post-condition. For example, "mkM stepfail" should not be passed to "everywhereM" as it will fail for all but one term pattern; see "recovered" for a way to massage "stepfail" accordingly. c) somewhere Descends into term in a top-down manner, and stops in a given branch when the argument succeeds for the subterm at hand. To this end, it takes an argument that is perfectly intended to fail for certain term patterns. Thanks to the employment of gmapF, the traversal scheme recovers from failure when mapping over the immediate subterms while insisting success for at least one subterm (say, branch). This scheme is appropriate if you want to make sure that a given rewrite step was actually used in a traversal. So failure of the traversal would mean that the argument failed for all subterms. Contributed by Ralf Laemmel, ralf@cwi.nl -} import Test.HUnit import Data.Generics import Control.Monad -- Two mutually recursive datatypes data T1 = T1a Int | T1b T2 deriving (Typeable, Data) data T2 = T2 T1 deriving (Typeable, Data) -- A rewrite step with identity as catch-all case stepid (T1a 42) = T1a 88 stepid x = x -- The same rewrite step but now with failure as catch-all case stepfail (T1a 42) = Just (T1a 88) stepfail _ = Nothing -- We can let recover potentially failing generic functions from failure; -- this is illustrated for a generic made from stepfail via mkM. recovered x = mkM stepfail x `mplus` Just x -- A test term that comprehends a redex term42 = T1b (T2 (T1a 42)) -- A test term that does not comprehend a redex term37 = T1b (T2 (T1a 37)) -- A number of traversals result1 = everywhere (mkT stepid) term42 -- rewrites term accordingly result2 = everywhere (mkT stepid) term37 -- preserves term without notice result3 = everywhereM (mkM stepfail) term42 -- fails in a harsh manner result4 = everywhereM (mkM stepfail) term37 -- fails rather early result5 = everywhereM recovered term37 -- preserves term without notice result6 = somewhere (mkMp stepfail) term42 -- rewrites term accordingly result7 = somewhere (mkMp stepfail) term37 -- fails to notice lack of redex tests = gshow ( result1, ( result2, ( result3, ( result4, ( result5, ( result6, ( result7 ))))))) ~=? output output = "((,) (T1b (T2 (T1a (88)))) ((,) (T1b (T2 (T1a (37)))) ((,) (Nothing) ((,) (Nothing) ((,) (Just (T1b (T2 (T1a (37))))) ((,) (Just (T1b (T2 (T1a (88))))) (Nothing)))))))"