使用折叠编写monad动作

让我们来看一个(Monad m) => a -> m a类型的函数。例如：使用折叠编写monad动作

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 =刚（X + 1），但在现实世界中失败：

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

来源

2010-02-10 sastanin

如果您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

来源

2010-02-10 18:01:05

好吧，如果你运行更多的迭代，仍然会出现同样的问题： ghci> iterateM_n 1000000（Just。（+1））3 \ n Just ***异常：堆栈溢出\ n ghci> iterateM_n'1000000（+） 0（Just。（+1））3 \ n Just ***例外：堆栈溢出\ n – sastanin 2010-02-10 18:09:23

@jetxee更新！ – 2010-02-10 19:20:28

我喜欢用'-XBangPatterns'而不是'seq' :-)无论如何，如果'f'是严格的，那么在我的答案中就不需要'>> =！'。既然看起来OP的'f'不是，这可能会有所帮助。 – ephemient 2010-02-10 20:10:09

我想出了这一点：

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

但它也溢出大数n堆栈。我没有时间，现在寻找到更:-(

来源

2010-02-10 15:13:22 liwp

无论如何，感谢尝试。 – sastanin 2010-02-10 15:22:40

我可能会创建的现有功能的一些严格的变种。

{-# 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-10 15:55:12 ephemient

该解决方案似乎运行良好，但并不比timesStrict更好，所以它也不是可扩展的。我必须深入研究。谢谢。 – sastanin 2010-02-10 20:00:30

使用折叠编写monad动作

回答

相关问题