Actions monades avec la composition des plis

Question

Prenons une fonction de type (Monad m) => a -> m a. Par exemple:

ghci> let f x = Just (x+1)

Je voudrais pouvoir appliquer un certain nombre de fois. La première chose que j'ai essayé était

ghci> let times n f = foldr (>=>) return $ replicate n f

Le problème est que cela ne fonctionnera pas pour les grands n:

ghci> 3 `times` f $ 1
Just 4
ghci> 1000000 `times` f $ 1
Just *** Exception: stack overflow

Il ne fonctionne pas aussi dans l'autre sens:

ghci> let timesl n f = foldl' (<=<) return $ replicate n f
ghci> 3 `timesl` f $ 1
Just 4
ghci> 1000000 `timesl` f $ 1
Just *** Exception: stack overflow

En fait, ce qui fonctionne utilise l'opérateur de ($!) de rigueur

ghci> let timesStrict n f = foldr1 ((>=>) . ($!)) $ replicate n f
ghci> 3 `timesStrict` f $ 1
Just 4
ghci> 10000000 `timesStrict` f $ 1
Just 10000001

Y at-il une solution plus agréable ou plus idiomatiques? Ou probablement plus strict? Je reste facilement obtenir si pile déborde f est une fonction poids lourd.

UPD: Je trouve que l'écriture times sous une forme pointful ne résout pas le problème de la composition des actions monades lourd poids non plus. Cela fonctionne pour f x = Just (x + 1), mais échoue dans le monde réel:

times f 0 a = return a
times f i a = (f $! a) >>= times f (i - 1)

Answer 1

Si vous faites f stricte comme dans

f x = let y = x+1 in y `seq` Just y

ou

-- remember to enable -XBangPatterns
f !x = Just (x+1)

et laisser le reste seul, votre code fonctionne dans l'espace constant (quoique lentement), même avec une très grande n:

ghci> times 4000000000 f 3
Just 4000000003

Answer 2

Je serais probablement créer des variantes plus strictes des fonctions existantes.

{-# LANGUAGE BangPatterns #-}
iterate' f !x = x : iterate' f (f x)
ma >>=! f = do !a <- ma; f a
times' n f a = iterate' (>>=! f) (return a) !! n

Peut-être que vos problèmes découlent du fait que seq n'évalue le premier argument de WHNF? Si vous travaillez sur une structure complexe, vous devrez peut-être un plus profond seq, comme deepseq .

Answer 3

Je suis venu avec ceci:

 last $ take n $ iterate (>>= f) $ Just 1

Mais il déborde aussi la pile sur un grand nombre de n. Je n'ai pas le temps maintenant de regarder en plus: - (