7

SYB (または他の Haskell ジェネリック パッケージ)を使用して、サブ計算の環境を変更するためにReader使用するモナドに変換を作成するにはどうすればよいですか? and (with ) のlocal型は、サブ計算をラップする(of type )の使用をサポートしていないようです。可能であれば、「標準」/「既製品」の変換を使用するソリューションを希望します。GenericMeverywhereMa -> m alocalm 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)

埋め込まれたすべてのs を、それらをラップする sIntの数よりも大きな値でインクリメントする再帰関数:Binder

-- 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し、ReaderSYB を使用して定型文の再帰ケースを自動的に処理することです(:@)。

SYB ではなくweaken1、環境を使用したの書き換え:Reader

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 ExpVar
  • ケースはLam再帰の前に環境を変更します:ここでeverywhereMは機能しません(私が知る限り)。Binder型は をどこで使用する必要があるかを示しているため、特定のケースlocalに適用することを望むかもしれませんが、その方法がわかりません。mkMBinder Exp -> Reader Int (Binder Exp)

上記のコードを含む、より多くの例を含む Gist を次に示します。

4

1 に答える 1

4

新しい 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ています。違いは、 を使用して結果を変換することです。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 ライブラリ コードを深く掘り下げる必要がありました。

繰り返しますが、上記のコードを含む、より多くの例を含む Gist があります。

于 2013-05-29T05:30:49.363 に答える