我想知道是否可以使用 Control.Arrow.loop 实现阶乘。loop :: ArrowLoop a => a (b, d) (c, d) -> a b c
一个明显的想法是实现一个以某种方式终止的分支(一个分支,其中对的第一个元素(类型 c
)不依赖于对的第二个元素(类型 d
))。
在我看来,这是无法完成的,因为我们无法在第一次迭代期间将任何 bool 函数应用于该对的第二个元素(类型 d
),因为它会导致无限递归,所以它只会给我们留下参数(类型 b
),但任何 bool 函数的结果都不会因迭代而有所不同(参数不会改变),因此,它要么立即终止,要么根本不终止。
我的另一个想法是创建无穷无尽的阶乘,但这似乎也不真实,因为再一次,这个论点无法改变。
所以,我有3个问题:
Control.Arrow.loop
实现阶乘的概念? ? 最佳答案
我从未真正使用过ArrowLoop
之前,loop
很酷。
这是使用 loop
实现的阶乘:
fact :: Integer -> Integer
fact =
loop $ \(n, f) ->
( f n 1
, \i acc ->
if i > 0
then f (i - 1) (i * acc)
else acc)
试一试吧:
λ> fact <$> [1..11]
[1,2,6,24,120,720,5040,40320,362880,3628800,39916800]
我不知道我是否可以回答您的第一个问题,但对于第三个问题,这显然是可能的。对于可以帮助您的概念,我认为解决点是您正在寻找的那个。例如,您可以从尝试这个开始;)
λ> import Data.Function
λ> fix error
一旦你按够了
Ctrl+C
您可以使用固定点编写阶乘:λ> let fact = fix $ \ f i -> if i > 1 then i * f (i - 1) else i
λ> fact <$> [1..11]
[1,2,6,24,120,720,5040,40320,362880,3628800,39916800]
编辑
似乎对答案进行一些扩展可能会有所帮助。
首先让我们看一下
fact
的另一种更好的(由于尾递归)实现。使用 fix
,所以我们可以看到它与使用 loop
的实现相比如何:factFix :: Integer -> Integer
factFix n =
fix
(\f ->
\i acc ->
if i > 0
then f (i - 1) (i * acc)
else acc)
n
1
我们可以看到它并不遥远。在这两种情况下,我们都会得到
f
作为参数,我们返回一个使用它的函数 f
,实际上,返回的非递归函数在这两种情况下都是相同的。为清楚起见,让我们在两个地方都将其提取为重用:factNoRec :: (Ord p, Num p) => (p -> p -> p) -> p -> p -> p
factNoRec f i acc =
if i > 0
then f (i - 1) (i * acc)
else acc
factLoop :: Integer -> Integer
factLoop n = loop (\(k, f) -> (f k 1, factNoRec f)) n
factFix :: Integer -> Integer
factFix n = fix (\f -> factNoRec f) n 1
希望现在它们是真正相关的概念更加明显。
研究
fix
的实现和 loop
(至少对于函数,因为还有 mfix
和循环 Kleisli
)提供了对它们关系的更多洞察:λ> fix f = let x = f x in x
λ> loop f b = let (c,d) = f (b,d) in c
他们真的很亲近。
类型签名怎么样:
λ> :t fix
fix :: (t -> t) -> t
λ> :t loop
loop :: ((b, d) -> (c, d)) -> b -> c
那些看起来不一样。但是如果你在
fact
中做一点统一你会看到 fix
和 loop
获取类型:λ> :t fix :: ((a -> b -> c) -> (a -> b -> c)) -> a -> b -> c
λ> :t loop :: ((b, a -> b -> c) -> (c, a -> b -> c)) -> b -> c
所有
a
b
和 c
成为全部Integer
最后,但是查看类型变量可以更好地了解正在发生的事情。真正发生的事情只是通过定点组合器进行递归。
关于haskell - 如何通过 Control.Arrow.loop 实现阶乘?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57741786/