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

How can I use SYB (or some other Haskell generics package), to write a transformation in a Reader monad that uses local to modify the environment for subcomputations? The types of GenericM and everywhereM (with a -> ma ) don't seem to support the use of local (of type ma -> ma ) to wrap a subcomputation. I would like a solution that uses "standard" / "off the shelf" transformations if possible.

A Representative 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 increments all the embedded Int s with values larger than the number of Binder s that wrap 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'):
  w i (Var j)          = wVar i j
  -- Boilerplate recursive case:
  w i (e1 :@ e2)       = w i e1 :@ w i e2
  -- Interesting recursive case: modify the environment:
  w i (Lam (Binder e)) = Lam (Binder (w (succ i) e))

wVar :: Int -> Int -> Exp
wVar i j | i <= j    = Var (succ j)
         | otherwise = Var j

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

A rewrite of weaken1 , using a Reader environment, but not SYB:

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

The point of the example:

  • the (:@) case is typical boilerplate recursion: everywhereM works here automatically.
  • the Var case uses the environment, but does not modify it: everywhereM works here, by applying mkM to a Exp -> Reader Int Exp specific to the Var case.
  • the Lam case modifies the environment before recursion: everywhereM does not work here (as far as I can tell). The Binder type tells us where we need to use local , so that we might hope to apply mkM to a Binder Exp -> Reader Int (Binder Exp) specific case, but I can't figure out how.
  • Here is a Gist with more examples, including the above code.


    Here is a solution by creating a new SYB traversal, everywhereMM :

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

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

    Now we can write a weaken3 . The idea is to combine a standard GenericM for the Var case of Exp with a new GenericMM that applies local in the Binder case:

    type W = Reader Int
    weaken3 :: Exp -> Exp
    weaken3 e = runReader (w e) 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 i j
      v e = return e
    

    But this solution is somewhat unsatisfying: creating the new traversal required digging deeply into the SYB library code.

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

    链接地址: http://www.djcxy.com/p/71724.html

    上一篇: .net MVC从控制器传递linq数据来查看

    下一篇: 如何使用`local`和`Reader` monad和Scrap您的Boilerplate(SYB)?