Haskell's Scrap Your Boilerplate (SYB) - применение преобразования только один раз, а не везде

Question

Какой лучший способ применить преобразование к дереву только один раз вместо everywhere используя SYB? Например, в следующем упрощенном выражении есть несколько случаев Var "x"и я хочу заменить первый экземпляр Var "y" только.

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

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

Это не может быть сделано с помощью everywhere комбинатор, так как он будет пытаться преобразовать все экземпляры Var "x" в Var "y",

РЕДАКТИРОВАТЬ (после публикации): похоже somewhere это то, что я ищу.

Answer 1

Будучи новичком в SYB, мой ответ больше похож на предположение, но, похоже, работает.

Комбинатор somewhere рекомендованный Нилом Брауном, вероятно, не делает именно то, что вы хотите. Это определяется как

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

Answer 2

Да, я думаю somewhere (mkMp mySpecificFunction) Это следует делать, если вы используете монаду MonadPlus и добьетесь успеха, когда найдете то, что ищете.

Гибкая, но хакерская альтернатива заключается в использовании everywhereM с государственной монадой, которая может хранить Boolean (или магазин Maybe MyFunc или что-то еще) и применить преобразование в зависимости от состояния True или же Just myFunc - таким образом, когда вы закончите (например, после применения преобразования один раз), вы просто измените состояние, чтобы быть False/Nothing,