Componer acciones monad con pliegues

Question

Vamos a tomar en función del tipo (Monad m) => a -> m a. Por ejemplo:

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

Me gustaría ser capaz de aplicarlo cualquier número de veces. Lo primero que intenté fue

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

El problema es que no funciona con gran n:

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

No funciona también a la inversa:

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 realidad, lo que funciona es usar el operador ($!) rigurosidad

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

¿Hay una solución mejor o más idiomática? O probablemente una más estricta? Todavía consigo fácilmente desbordamientos de pila si f es una función de gran peso.

UPD: He encontrado que la escritura times en una forma pointful no resuelve el problema de componer acciones monádicos pesada de peso ni. Esto funciona para f x = Just (x + 1) pero fracasa en el mundo real:

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

Answer 1

Si comete f estricta como en

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

o

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

y dejar el resto solo, su código se ejecuta en el espacio constante (aunque lentamente), incluso con muy grande n:

ghci> times 4000000000 f 3
Just 4000000003

Answer 2

probablemente me crear algunas variantes más estrictas de las funciones existentes.

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

Tal vez sus problemas se derivan del hecho de que seq sólo evalúa el primer argumento de WHNF? Si está trabajando en una estructura compleja, es posible que necesite un seq más profundo, como deepseq .

Answer 3

Se me ocurrió esto:

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

Pero también se desborda la pila sobre un gran número de n. No tengo el tiempo en este momento para buscar en ella más: - (