4

让我们使用 type 的函数(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用有针对性的形式写作也不能解决编写重量级单子动作的问题。这适用于 fx = Just (x+1) 但在现实世界中失败:

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

3 回答 3

4

如果你f严格如

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

或者

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

剩下的就不用管了,即使非常大,您的代码也会在恒定空间中运行(尽管速度很慢)n

ghci> 次 4000000000 f 3
仅 4000000003
于 2010-02-10T18:01:05.547 回答
2

我可能会为现有函数创建一些更严格的变体。

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

于 2010-02-10T15:55:12.103 回答
1

我想出了这个:

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

但它也会在大量n. 我现在没有时间进一步研究它:-(

于 2010-02-10T15:13:22.713 回答