How to use the `local` and` Reader` monad with Scrap Your Boilerplate (SYB)?

Question

How can I use SYB (or some other Haskell generic package) to write a conversion in the Reader monad that uses local to change the environment for subcomplexes? The GenericM and everywhereM types (with a -> ma ) do not seem to support the use of local (such as ma -> ma ) to carry the subcom. I would like a solution that used "standard" / "off-shelf" conversions, if possible.

Typical example

A (mysterious) recursive data type:

 {-# LANGUAGE DeriveDataTypeable , Rank2Types , ViewPatterns #-} import Data.Generics import Control.Applicative import Control.Monad.Reader import Control.Arrow data Exp = Var Int | Exp :@ Exp | Lam (Binder Exp) deriving (Eq , Show , Data , Typeable) newtype Binder a = Binder a deriving (Eq , Show , Data , Typeable) 

A recursive function that increases all nested Int values ​​by more than the number of Binder that wraps them:

 -- Increment all free variables: -- If G |- e:B then G,A |- weaken e:B. weaken1 :: Exp -> Exp weaken1 = w 0 where w :: Int -> Exp -> Exp -- Base case: use the environment ('i'): wi (Var j) = wVar ij -- Boilerplate recursive case: wi (e1 :@ e2) = wi e1 :@ wi e2 -- Interesting recursive case: modify the environment: wi (Lam (Binder e)) = Lam (Binder (w (succ i) e)) wVar :: Int -> Int -> Exp wVar ij | i <= j = Var (succ j) | otherwise = Var j 

The goal is to put the parameter i in weaken1 into the Reader environment and use SYB to automatically handle the recursive case with the template for (:@) .

Rewrite weaken1 using Reader , but not SYB:

 weaken2 :: Exp -> Exp weaken2 e = runReader (we) 0 where w :: Exp -> Reader Int Exp w (Var j) = do i <- ask return $ wVar ij w (e1 :@ e2) = (:@) <$> w e1 <*> w e2 w (Lam (Binder e)) = Lam . Binder <$> local succ (we) 

Example point:

• Case (:@) is a typical template recursion: everywhereM works here automatically.
• the Var case uses the environment, but does not modify it: everywhereM works here, applying mkM to Exp -> Reader Int Exp specific to the Var case.
• The Lam case changes the environment before recursion: everywhereM doesn't work here (as far as I can tell). The Binder type tells us where we need to use local , so we can hope to apply mkM to the specific case of Binder Exp -> Reader Int (Binder Exp) , but I cannot figure out how to do this.

Here is an example with examples , including the code above.

Answer 1

Here is the solution by creating a new SYB workaround, everywhereMM :

 newtype MM mx = MM { unMM :: mx -> mx } mkMM :: (Typeable a , Typeable b) => (ma -> ma) -> mb -> mb mkMM t = maybe id unMM (gcast (MM t)) -- Apply a 'GenericM' everywhere, transforming the results with a -- 'GenericMM'. type GenericMM m = Data a => ma -> ma everywhereMM :: Monad m => GenericMM m -> GenericM m -> GenericM m everywhereMM mm mx = mm (m =<< gmapM (everywhereMM mm m) x) 

The everywhereMM and mkMM similar to everywhereM and mkM in Data.Generics.Schemes and Data.Generics.Aliases ; the difference is that everywhereMM uses mm , a GenericMM to convert the result.

Now we can write weaken3 . The idea is to combine the GenericM standard for the Var Exp case with the new GenericMM , which uses local in the Binder case:

 type W = Reader Int weaken3 :: Exp -> Exp weaken3 e = runReader (we) 0 where w :: GenericM W w = everywhereMM (mkMM b) (mkM v) b :: W (Binder Exp) -> W (Binder Exp) b = local succ v :: Exp -> W Exp v (Var j) = do i <- ask return $ wVar ij ve = return e 

But this solution is somewhat unsatisfactory: the creation of a new workaround requires deep penetration into the SYB library code.

Again, here is a Gist with a lot of examples , including the code above.