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

Возьмем функцию типа (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)

reduce lazy-evaluation haskell monads
person sastanin    schedule 10.02.2010    source источник

Ответы (3)


arrow_upward
4
arrow_downward

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

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

or

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

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

ghci> times 4000000000 f 3
Just 4000000003
person Greg Bacon    schedule 10.02.2010
comment
Ну, та же проблема, если вы запустите больше итераций: ghci› iterateM_n 1000000 (Just . (+1)) 3 \n Just *** Исключение: переполнение стека \n ghci› iterateM_n' 1000000 (+) 0 (Just . ( +1)) 3 \n Просто *** Исключение: переполнение стека \n - person sastanin; 10.02.2010
comment
Мне нравится использовать -XBangPatterns вместо seq :-) В любом случае, если f строгое, то >>=! в моем ответе не нужно. Поскольку кажется, что f ОП нет, это может помочь. - person ephemient; 10.02.2010
comment
Спасибо! Принятый. Это действительно работает с (Just . (+1)). У меня все еще есть проблемы с моей реальной функцией, но, по крайней мере, теперь я вижу, что может помочь. - person sastanin; 12.02.2010
comment
@jetxee Спасибо! Как сделать эту функцию строгой? кажется отличным дополнительным вопросом. - person Greg Bacon; 12.02.2010

arrow_upward
2
arrow_downward

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

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

person ephemient    schedule 10.02.2010
comment
Это решение работает хорошо, но не лучше, чем timesStrict, поэтому оно также не является масштабируемым. Я должен заглянуть в deepseq. Спасибо. - person sastanin; 10.02.2010

arrow_upward
1
arrow_downward

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

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

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

person liwp    schedule 10.02.2010