Haskell rec 关键字如何工作？

Question

在箭头do表示法中，您可以使用rec关键字来编写递归定义。举例来说：

rec
    name <- function -< input
    input <- otherFunction -< name

这如何评估？看起来它会进入无限循环或其他什么。我知道它的计算结果为循环箭头组合器，但我也不明白它是如何工作的。

编辑：那个权力的例子真的很有帮助。不过，你会如何用 do 符号来写它呢？我假设你需要使用rec.

Answer 1

这种神奇的效果是由于 haskells 的懒惰造成的。您可能知道，Haskell 在需要时计算值，而不是在定义时计算值。因此，如果您不需要直接输入值或稍后输入值，则此方法有效。

rec是使用ArrowLoop的loop函数实现的。其定义如下：

class Arrow a => ArrowLoop a where
        loop :: a (b,d) (c,d) -> a b c

instance ArrowLoop (->) where
        loop f b = let (c,d) = f (b,d) in c

可以看到：输出只是作为输入反馈回来的。它只会被计算一次，因为 Haskell 只会在需要时计算 d 。

这是如何直接使用loop组合器的实际示例。该函数计算其参数的所有幂：（

powers = loop $ \(x,l) -> (l,x:map(*x)l)

您也可以这样写：powers x = fix $ (x :) .map (*x)）

它是如何工作的？那么，无限的权力列表就在 l 参数中。评价看起来像这样：

powers = loop $ \(x,l) -> (l,x:map(*x)l) ==>
powers b = let (c,d) = (\(x,l) -> (l,x:map(*x)l)) (b,d) in c ==>
powers b = let (c,d) = (d,b:map(*b)d) in d ==> -- Now  we apply 2 as an argument
powers 2 = let (c,d) = (d,2:map(*2)d) in d ==>
         = let (c,(2:d)) = (d,2:map(*2)d) in c ==>
         = let (c,(2:4:d)) = ((2:d),2:map(*2)(2:d)) in c ==>
         = let (c,(2:4:8:d)) = ((2:4:d),2:map(*2)(2:4:d)) in  ==> -- and so on

Answer 2

这是一个真实的例子：

loop f b = let (c,d) = f (b,d) in c

f (b,d) = (drop (d-2) b, length b)

main = print (loop f "Hello World")

这个程序输出“ld”。函数“loop f”接受一个输入“b”并创建一个输出“c”。 “f”正在做的是研究“b”以产生“长度b”，该长度返回到循环并绑定到“d”。

在“循环”中，这个“d=长度b”被输入到“f”中，在“f”中用于drop的计算。

这对于构建不可变的双向链表（也可能是循环的）等技巧很有用。它对于遍历“b”一次以产生一些分析“d”（例如长度或最大元素）并构建依赖于“d”的新结构“c”也很有用。惰性避免了必须遍历“b”两次。