Haskell rec关键字如何工作？

Question

在箭头符号中,您可以使用rec关键字来编写递归定义.例如:

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

这怎么能评估？它似乎只会进入一个无限循环或其他东西.我知道它评估循环箭头组合器,但我不明白它是如何工作的.

编辑:权力示例非常有用.但是你怎么用写符号来写呢？我假设你需要使用rec.

Answer 1

由于haskells的懒惰,这一点魔法起作用.您可能知道,Haskell会在需要时评估值,而不是在定义时.因此,如果您不需要直接或稍后输入的值,则此方法有效.

rec使用loop函数实现ArrowLoop.它的定义如下:

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',在那里它被用于计算中.

这对于构建不可变双链表(也可能是循环表)等技巧非常有用.对于遍历'b'一次既产生一些分析'd'(例如长度或最大元素)以及构建依赖于'd'的新结构'c'也是有用的.懒惰避免了必须两次遍历'b'.