Составление монадных действий со складками - PullRequest
Новая
       21

Составление монадных действий со складками

4 голосов
/ 10 февраля 2010

Давайте возьмем функцию типа (Monad m) => a -> m a. Например: 

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

Я хотел бы иметь возможность применять его любое количество раз. Первое, что я попробовал, было 

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

Проблема в том, что он не будет работать для больших n: 

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

Это не работает и по-другому: 

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

На самом деле, то, что работает, использует ($!) оператор строгости 

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

Есть ли более приятное или более идиоматическое решение? Или, возможно, более строгий? Я по-прежнему легко получаю переполнение стека, если f является тяжелой функцией.

UPD: Я обнаружил, что написание times в точечной форме также не решает проблему составления монадических действий большого веса. Это работает для f x = Just (x + 1), но терпит неудачу в реальном мире: 

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

Ответы [ 3 ]

4 голосов
/ 10 февраля 2010

Если вы сделаете f строгим, как в 

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

или 

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

и оставьте все в покое, ваш код работает в постоянном пространстве (хотя и медленно) даже при очень большом n: 

ghci> times 4000000000 f 3
Just 4000000003
2 голосов
/ 10 февраля 2010

Возможно, я бы создал несколько более строгих вариантов существующих функций. 

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

Возможно, ваши проблемы проистекают из того факта, что seq оценивает только первый аргумент WHNF? Если вы работаете со сложной структурой, вам может потребоваться более глубокий seq, например deepseq .

1 голос
/ 10 февраля 2010

Я придумал это: 

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

Но он также переполняет стек при большом количестве n. У меня сейчас нет времени, чтобы разобраться в этом подробнее: - (

...