如何使用 SYB(或其他一些 Haskell 泛型包)在用于修改子计算环境的Reader
monad 中编写转换?和(with )local
的类型似乎不支持使用(of type ) 来包装子计算。如果可能的话,我想要一个使用“标准”/“现成”转换的解决方案。GenericM
everywhereM
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)
一个递归函数,它将所有嵌入Int
的 s 递增,其值大于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,包括上面的代码。