Haskell's Scrap Your Boilerplate (SYB) - applica la trasformazione una sola volta anziché ovunque

Question

Qual è il modo migliore per applicare una trasformazione a un albero una sola volta invece di everywhere utilizzando SYB? Ad esempio, nella seguente espressione semplificata, esistono diverse istanze di Var "x" e desidero sostituire la prima istanza solo con Var "y".

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

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

Questo non può essere fatto utilizzando la everywhere combinatore in quanto cercherà di trasformare tutte le istanze di Var "x"-Var "y".

MODIFICA (dopo la pubblicazione): Sembra che somewhere sia quello che sto cercando.

Answer 1

Essendo un principiante SYB, la mia risposta è più simile a una supposizione, ma sembra funzionare.

Combinator somewhere consigliato da Neil Brown probabilmente non fa esattamente quello che vuoi. E 'defined come

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

dove

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

Ma dobbiamo trasformare al massimo una volta. Per questo sembra che gmapMo sarà meglio:

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

così ho fatto la mia combinatore:

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

Se la sostituzione non riesce, restituisce mzero, altrimenti restituisce il risultato sostituito. Se non vi interessa se la sostituzione non riesce (nessun risultato), si potrebbe usare qualcosa come

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

Con questi, possiamo fare alcune sostituzioni:

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

Sì, penso che lo somewhere (mkMp mySpecificFunction) dovrebbe farlo, se si utilizza MonadPlus e si riesce a farlo quando trova ciò che si sta cercando.

Un flessibile, ma hacky alternativa è di usare everywhereM con una monade Stato che può memorizzare un Boolean (o conservare Maybe MyFunc o qualsiasi altra cosa) e applicare la trasformazione a seconda dello stato di essere True o Just myFunc - in questo modo, quando si è fatto (ad esempio dopo aver applicato la trasformazione una volta), è sufficiente modificare lo stato in False/Nothing.