Composizione azioni monade con pieghe

Question

Diamo una funzione di tipo (Monad m) => a -> m a. Ad esempio:

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

Mi piacerebbe essere in grado di applicare qualsiasi numero di volte. La prima cosa che ho provato è stato

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

Il problema è che non funzionerà per grandi n:

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

Non funziona anche nell'altro senso:

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

In realtà, ciò che funziona sta usando operatore ($!) rigore

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

C'è una soluzione più o più idiomatica? O probabilmente un più rigoroso uno? Ho ancora ottenere facilmente overflow dello stack se f è una funzione pesante.

UPD: Ho trovato che scrivere times in una forma pointful non risolve il problema di comporre pesanti azioni monadici né. Questo funziona per f = x Just (x + 1) ma non riesce nel mondo reale:

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

Answer 1

Se si effettua f rigoroso come in

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

o

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

e lasciare il resto da solo, il codice viene eseguito in uno spazio costante (anche se lentamente) anche con molto grande n:

ghci> times 4000000000 f 3
Just 4000000003

Answer 2

Probabilmente mi creo alcune varianti più rigorose di funzioni esistenti.

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

Forse i vostri problemi derivano dal fatto che seq valuta solo il primo argomento di WHNF? Se si sta lavorando su una struttura complessa, potrebbe essere necessario un seq più profondo, come deepseq .

Answer 3

sono arrivato fino a questo:

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

Ma trabocca anche lo stack su un gran numero di n. Non ho il tempo adesso di esaminare più: - (