如何使用`local`和`Reader` monad with Scrap Your Boilerplate(SYB)？

Question

我如何使用SYB(或其他一些Haskell泛型包)在Readermonad中编写转换,用于local修改子计算的环境？类型GenericM和everywhereM(with a -> m a)似乎不支持使用local(类型m a -> m a)来包装子计算.如果可能的话,我想要一个使用"标准"/"现成"转换的解决方案.

代表性的例子

一种(神秘的)递归数据类型:

{-# 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)

一个递归函数,它使所有嵌入的Ints 递增,其值大于Binder包装它们的s 的数量:

-- 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

目标是将i参数weaken1放在一个Reader环境中并使用SYB自动处理样板的递归情况(:@).

weaken1使用Reader环境而不是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)

示例的要点:

• 这种(:@)情况是典型的样板递归:everywhereM在这里自动工作.
• 的Var情况下,使用环境,但不修改它:everywhereM在这里工作,通过应用mkM到Exp -> Reader Int Exp具体的Var情况.
• 的Lam情况下修改递归前的环境:everywhereM没有没有在这里工作(据我可以告诉).该Binder类型告诉我们,我们需要使用local,所以我们可能希望应用mkM到Binder Exp -> Reader Int (Binder Exp)具体情况,但我无法弄清楚如何.

这是一个包含更多示例的Gist,包括上面的代码.

Answer 1

这是通过创建新的 SYB 遍历的解决方案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)

everywhereMM和 的定义与和中的和mkMM类似；不同之处在于使用, a来转换结果。everywhereMmkMData.Generics.SchemesData.Generics.AliaseseverywhereMMmmGenericMM

现在我们可以写一个weaken3. GenericM这个想法是将案例Var的 标准与适用于案例的Exp新标准结合起来：GenericMMlocalBinder

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

但这个解决方案有些不令人满意：创建新的遍历需要深入挖掘 SYB 库代码。

同样，这里有一个包含更多示例的要点，包括上面的代码。