用褶皱构成monad动作 [英] Composing monad actions with folds
问题描述
让我们来看一个类型为(Monad m)=>的函数。 a - > m a
。例如:
ghci>让fx = Just(x + 1)
我希望能够将其应用于任何数字的时代。我试过的第一件事是:
ghci>让times nf = foldr(> =>返回$ replicate nf
问题在于它不适用于大型 n
:
ghci> 3`次`f $ 1
只需4
ghci> 1000000`times` f $ 1
只是***例外:堆栈溢出
另一种方式也行不通:
ghci>让timesl n f = foldl'(< =<)return $ replicate n f
ghci> 3`timesl` f $ 1
只需4
ghci> 1000000`timesl` f $ 1
只是***例外:堆栈溢出
实际上, ($!)
严格操作符
ghci>让timesStrict n f = foldr1((> =>)。($!))$ replicate n f
ghci> 3`timesStrict` f $ 1
只需4
ghci> 10000000`timesStrict` f $ 1
只有10000001
是否有更好或更习惯的解决方案?或者可能更严格?如果 f
是一个重量级函数,我仍然很容易发生堆栈溢出。
$ b UPD:我发现以有意义的形式写
次
并不能解决构成重量级一元动作的问题。这适用于fx = Just(x + 1),但在现实世界中失败: times f 0 a = return a
次fia =(f $!a)>> =次f(i-1)
如果您使 f
strict $ b $
fx = let y = x + 1 in y`seq`只需
或
- 记得启用-XBangPatterns
f!x = Just(x + 1)
并保留其余部分,即使使用非常大的 n
:
ghci> times 4000000000 f 3
Just 4000000003
Let's take a function of type (Monad m) => a -> m a
. For example:
ghci> let f x = Just (x+1)
I'd like to be able to apply it any number of times. The first thing I tried was
ghci> let times n f = foldr (>=>) return $ replicate n f
The problem is that it won't work for large n
:
ghci> 3 `times` f $ 1
Just 4
ghci> 1000000 `times` f $ 1
Just *** Exception: stack overflow
It doesn't work also the other way:
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
Actually, what works is using ($!)
strictness operator
ghci> let timesStrict n f = foldr1 ((>=>) . ($!)) $ replicate n f
ghci> 3 `timesStrict` f $ 1
Just 4
ghci> 10000000 `timesStrict` f $ 1
Just 10000001
Is there a nicer or more idiomatic solution? Or probably a stricter one? I still easily get stack overflows if f
is a heavy-weight function.
UPD: I found that writing times
in a pointful form does not solve the problem of composing heavy-weight monadic actions neither. This works for f x = Just (x+1) but fails in the real world:
times f 0 a = return a
times f i a = (f $! a) >>= times f (i - 1)
If you make f
strict as in
f x = let y = x+1 in y `seq` Just y
or
-- remember to enable -XBangPatterns
f !x = Just (x+1)
and leave the rest alone, your code runs in constant space (albeit slowly) even with very large n
:
ghci> times 4000000000 f 3 Just 4000000003
这篇关于用褶皱构成monad动作的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!