Composition d'actions monad avec des plis

Question

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

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

J'aimerais pouvoir l'appliquer autant de fois que vous le souhaitez. 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 ($!) opérateur 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 

Existe-t-il une solution plus sympa ou plus idiomatique? Ou probablement un plus strict? J'obtiens toujours facilement des débordements de pile si f est une fonction lourde.

UPD: J'ai trouvé qu'écrire times sous une forme pointue ne résout pas non plus le problème de composer des actions monadiques lourdes. 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 est exécuté dans l'espace constant (quoique lentement), même avec une très grande n:

ghci> times 4000000000 f 3 
Just 4000000003

Answer 2

je suis venu avec ceci:

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

Mais elle déborde aussi la pile sur un grand nombre de n. Je n'ai pas le temps en ce moment pour examiner plus :-(

Answer 3

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 seulement seq Evalue le premier argument de WHNF? Si vous travaillez sur une structure complexe, vous devrez peut-être un plus profond seq, comme deepseq.