Composing Monade Aktionen mit Falten

Question

Lassen Sie uns nehmen eine Funktion vom Typ (Monad m) => a -> m a. Zum Beispiel:

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

Ich möchte in der Lage sein, es beliebig oft anwenden. Das erste, was ich versuchte, war

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

Das Problem ist, dass es nicht Arbeit für großen n:

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

Es funktioniert nicht, auch in die andere Richtung:

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

Eigentlich, was funktioniert, ist mit ($!) Strikt Operator

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

Gibt es eine schönere oder mehr idiomatische Lösung? Oder vielleicht ein strengerer ein? Ich immer noch leicht bekommen Stapel überläuft, wenn f eine schwere Funktion ist.

UPD: Ich fand, dass das Schreiben times in einer pointful Form löst nicht das Problem der Zusammenschwergewichtigen monadischen Handlungen weder. Dies funktioniert für f x = Just (x + 1), aber nicht in der realen Welt:

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

Answer 1

Wenn Sie machen f streng wie in

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

oder

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

und den Rest allein, Ihr Code läuft in konstantem Raum (wenn auch langsam) auch bei sehr großen n:

ghci> times 4000000000 f 3
Just 4000000003

Answer 2

Ich würde wahrscheinlich schaffen einige strengere Varianten bestehender Funktionen.

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

Vielleicht stammen Ihre Probleme aus der Tatsache, dass seq wertet nur das erste Argument WHNF? Wenn Sie auf einer komplexen Struktur arbeiten, können Sie einen tieferen seq benötigen, wie deepseq .

Answer 3

kam ich mit diesem nach oben:

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

Aber er überläuft auch den Stapel auf eine große Anzahl von n. Ich habe nicht die Zeit haben, jetzt in sie aussehen: - (