Compondo ações mônada com dobras
-
19-09-2019 - |
Pergunta
Vamos dar uma função do tipo (Monad m) => a -> m a
. Por exemplo:
ghci> let f x = Just (x+1)
Eu gostaria de ser capaz de aplicá-lo qualquer número de vezes. A primeira coisa que eu tentei foi
ghci> let times n f = foldr (>=>) return $ replicate n f
O problema é que ele não vai funcionar para grandes n
:
ghci> 3 `times` f $ 1
Just 4
ghci> 1000000 `times` f $ 1
Just *** Exception: stack overflow
Não funciona também a outra maneira:
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
Na verdade, o que funciona é usando o operador ($!)
rigor
ghci> let timesStrict n f = foldr1 ((>=>) . ($!)) $ replicate n f
ghci> 3 `timesStrict` f $ 1
Just 4
ghci> 10000000 `timesStrict` f $ 1
Just 10000001
Existe uma agradável ou solução mais idiomática? Ou, provavelmente, uma norma mais rigorosa? Eu ainda chegar facilmente pilha transborda se f
é uma função peso-pesado.
UPD: eu achei que times
escrita de uma forma cheia de oportunidade não resolve o problema de compor peso-pesado ações monádicas nem. Isso funciona para f x = Just (x + 1), mas não no mundo real:
times f 0 a = return a
times f i a = (f $! a) >>= times f (i - 1)
Solução
Se você fizer f
estrita como na
f x = let y = x+1 in y `seq` Just y
ou
-- remember to enable -XBangPatterns
f !x = Just (x+1)
e deixar o resto sozinho, suas corridas de código no espaço constante (embora lentamente), mesmo com muito grande n
:
ghci> times 4000000000 f 3 Just 4000000003
Outras dicas
eu provavelmente criar algum rigorosa variantes de funções 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
Talvez os seus problemas derivam do fato de que seq
avalia apenas o primeiro argumento para WHNF? Se você está trabalhando em uma estrutura complexa, você pode precisar de um seq
mais profundo, como deepseq .
Eu vim com isso:
last $ take n $ iterate (>>= f) $ Just 1
Mas também transborda a pilha em um grande número de n
. Eu não tenho o tempo agora para pensar mais sobre isso: - (