5

将转换应用于树一次而不是everywhere使用 SYB 的最佳方法是什么？例如，在下面的简化表达式中，有几个 的实例Var "x"，我想用Var "y"only 替换第一个实例。

data Exp = Var String | Val Int | Plus Exp Exp |...

myExp = Val 5 `Plus` Var "x" `Plus` Val 5 `Plus` Var "x" ...

这不能使用everywhere组合器完成，因为它会尝试转换 to 的所有Var "x"实例Var "y"。

编辑（发布后）：看起来somewhere就是我要找的东西。

4

2 回答 2

3

作为一名 SYB 初学者，我的回答更像是猜测，但似乎可行。

Neil Brown 推荐的Combinatorsomewhere可能并不完全符合您的要求。它被定义为

-- | Apply a monadic transformation at least somewhere
somewhere :: MonadPlus m => GenericM m -> GenericM m

-- We try "f" in top-down manner, but descent into "x" when we fail
-- at the root of the term. The transformation fails if "f" fails
-- everywhere, say succeeds nowhere.
-- 
somewhere f x = f x `mplus` gmapMp (somewhere f) x

在哪里

-- | Transformation of at least one immediate subterm does not fail 
gmapMp :: forall m. MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a

但是我们最多需要转换一次。为此，这似乎gmapMo会更好：

-- | Transformation of one immediate subterm with success 
gmapMo :: forall m. MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a

所以我制作了自己的组合器：

{-# LANGUAGE DeriveDataTypeable, RankNTypes #-}
import Control.Monad
import Data.Maybe (fromMaybe)
import Data.Data
import Data.Typeable (Typeable)
import Data.Generics.Schemes
import Data.Generics.Aliases

-- | Apply a monadic transformation once.
once :: MonadPlus m => GenericM m -> GenericM m
once f x = f x `mplus` gmapMo (once f) x

如果替换失败，则返回mzero，否则返回替换结果。如果您不在乎替换是否失败（不匹配），您可以使用类似

once' :: (forall a. Data a => a -> Maybe a) -> (forall a. Data a => a -> a)
once' f x = fromMaybe x (once f x)

有了这些，我们可以做一些替换：

data Exp = Var String | Val Int | Plus Exp Exp
  deriving (Show, Typeable, Data)

myExp = Val 5 `Plus` Var "x" `Plus` Val 5 `Plus` Var "x"

replM :: (MonadPlus m) => Exp -> m Exp
replM (Var "x") = return $ Var "y"
replM t         = mzero

main = do
    -- `somewhere` doesn't do what we want:
    print $ (somewhere (mkMp replM) myExp :: Maybe Exp)

    -- returns `Just ..` if the substitution succeeds once,
    -- Nothing otherwise.
    print $ (once (mkMp replM) myExp :: Maybe Exp)
    -- performs the substitution once, if possible.
    print $ (once' (mkMp replM) myExp :: Exp)

    -- Just for kicks, this returns all possible substitutions
    -- where one `Var "x"` is replaced by `Var "y"`.
    print $ (once (mkMp replM) myExp :: [Exp])
于 2013-06-04T19:21:03.747 回答
2

是的，我认为somewhere (mkMp mySpecificFunction)应该这样做，如果您使用 MonadPlus monad 并在找到您要查找的内容时使其成功。

一个灵活但很老套的替代方法是使用everywhereM可以存储 a Boolean（或存储Maybe MyFunc或其他）并根据状态应用转换的 State monadTrue或者Just myFunc- 这样，当你完成时（例如，在应用一次转换之后），您只需将状态更改为False/ Nothing。

于 2013-06-04T08:32:09.607 回答