Złom Haskella złapał płytę kotła (SYB) - stosując transformację tylko raz zamiast wszędzie

Question

Jaki jest najlepszy sposób zastosowania transformacji do drzewa tylko raz zamiast everywhere przy użyciu SYB? Na przykład w następującym uproszczonym wyrażeniu istnieje kilka instancji Var "x" i chcę zastąpić pierwsze wystąpienie tylko Var "y".

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

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

ta nie może być wykonana przy użyciu everywhere COMBINATOR ponieważ będzie starał się przekształcić wszystkie instancje Var "x" do Var "y".

EDYCJA (po zaksięgowaniu): Wygląda na to, że szukam somewhere.

Answer 1

Sam będąc początkującym SYB, moja odpowiedź jest raczej domysłem, ale wydaje się działać.

Kombinator somewhere polecany przez Neila Browna prawdopodobnie nie robi dokładnie tego, co chcesz. To defined jak

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

gdzie

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

Ale musimy przekształcić co najwyżej raz. Do tego wydaje się, że będzie lepiej gmapMo:

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

Więc zrobiłem własną COMBINATOR:

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

Jeżeli substytucja nie powiedzie, zwraca mzero, w przeciwnym razie zwraca podstawiony wynik. Jeśli nie obchodzi czy substytucja nie powiedzie się (Nie znaleziono), można użyć coś jak

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

z tymi, możemy zrobić jakieś zamienniki:

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

Tak, myślę, że somewhere (mkMp mySpecificFunction) powinien to zrobić, jeśli używasz monady MonadPlus i sprawi, że się uda, gdy znajdzie to, czego szukasz.

Elastyczny ale hacky Alternatywą jest użycie everywhereM z monady państwa, która może przechowywać Boolean (lub przechowywać Maybe MyFunc lub cokolwiek) i zastosować przekształcenie w zależności od stanu będącego True lub Just myFunc - w ten sposób, gdy skończysz (np. po zastosowaniu transformacji raz), po prostu zmieniasz stan na False/Nothing.