对列表生成函数进行延迟评估？

Question

我现在正在阅读Graham Hutton编写的Haskell编程.

在第40页,提出了玩具素性测试:

factors :: Int -> [Int]
factors n = [x | x <- [1..n], n `mod` x == 0]

prime :: Int -> Bool
prime n = factors n == [1,n]

然后,作者继续解释如何

"确定一个数字不是素数不需要函数素数来产生它的所有因子,因为在惰性求值下False,只要产生一个或多个数字本身以外的任何因子,就会返回结果"

作为来自C和Java的人,我发现这令人震惊.我希望factors调用首先完成,将结果保存在堆栈中并将控制传递给调用函数.但显然这里正在执行一个非常不同的程序:列表理解必须有一个循环,factors并且prime正在检查添加到因子列表中的每个新元素的相等性检查.

这怎么可能？这对于程序的执行顺序是否更难以推理？

Answer 1

你发现它"令人震惊",因为你并不期待它.一旦你习惯了......好吧,实际上它仍然让人们过来.但是过了一会儿,你最终会把它包裹起来.

Haskell如何工作是这样的:当你调用一个函数时,没有任何反应!呼叫在某个地方被记下来,就是这样.这几乎没有时间.你的"结果"实际上只是一个"我欠你",告诉计算机运行什么代码来获得结果.请注意,不是整个结果; 只是它的第一步.对于像一个整数,还有就是只有一步.但是对于列表,每个元素都是一个单独的步骤.

让我向您展示一个更简单的例子:

print (take 10 ([1..] ++ [0]))

我采访了一位C++程序员,他对此感到"震惊".当然," ++[0]"部分必须"找到列表的末尾",然后才能将零添加到它之前？这段代码如何在有限的时间内完成？!

它看起来像这样建立[1..](在无穷列表),然后++[0]扫描该列表的末尾并插入一个零,然后take 10修剪掉只是第10个元素,然后将其打印.那当然会花费无限的时间.

所以这就是实际发生的事情.最外层的功能是take,这就是我们开始的地方.(我没想到,嗯？)定义take是这样的:

take 0 (   _) = []
take n (  []) = []
take n (x:xs) = x : (take (n-1) xs)

所以很明显10!= 0,所以第一行不适用.所以第二行或第三行都适用.所以现在take看[1..] ++ [0],看它是否是一个空列表,或者一个非空列表.

这里最外面的功能是(++).它的定义看起来类似于

(  []) ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

所以我们需要弄清楚哪个等式适用.左参数是空列表(第一行适用),或者不是(第二行适用).好吧,因为[1..]是无限列表,第二行总是适用.所以"结果" [1..] ++ [0]是1 : ([2..] ++ [0]).如你所见,这并没有完全执行; 但它执行得足以告诉这是一个非空列表.这就是所take关心的.

take 10 ([1..] ++ [0])
take 10 (1 : ([2..] ++ [0]))
1 : take 9 ([2..] ++ [0])
1 : take 9 (2 : ([3..] ++ [0]))
1 : 2 : take 8 ([3..] ++ [0])
1 : 2 : take 8 (3 : ([4..] ++ [0]))
1 : 2 : 3 : take 7 ([4..] ++ [0])
...
1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 10 : take 0 ([11..] ++ [0])
1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 10 : []

你看到这是如何解开的吗？

现在,返回到您的特定问题:(==)运算符采用一对列表并迭代它们,逐个元素地比较它们以确保它们相等.一旦发现差异,它会立即中止并返回false:

(  []) == (  []) = True
(x:xs) == (y:ys) = (x == y) && (xs == ys)
(   _) == (   _) = False

如果我们现在尝试,比方说prime 6:

prime 6
factors 6 == [1,6]
??? == [1,6]
1 : ??? == [1,6]
??? == [6]
2 : ??? == [6]
False

Answer 2

我会关注这一点:

这对于程序的执行顺序是否更难以推理？

是的,但评估的顺序在纯函数式编程中并不重要.例如:

(1 * 3) + (4 * 5)

问:首先执行哪个乘法？答:我们不在乎,结果是一样的.即使C编译器也可以在这里选择任何订单.

(f 1) + (f 2)

问:首先执行哪个函数调用？答:我们不在乎,结果是一样的.在这里,C编译器也可以选择任何订单.但是,在C中,函数f可能有副作用,使得上述总和的结果取决于评估的顺序.在纯函数式编程中,没有副作用,所以我们真的不在乎.

此外,懒惰允许语义保留任何函数定义的扩展.假设我们定义

f x = e -- e is an expression which can use x

我们打电话f 2.结果应该相同e{2/x},即e每次(自由)出现的地方x都被替换为2.这只是"展开定义",就像在数学中一样.例如,

f x = x + 4

-- f 2 ==> 2 + 4 ==> 6

但是,假设我们打电话f (g 2)来.懒惰使这相当于e{g 2/x}.再次,如在数学中.例如:

f x = 42
g n = g (n + 1)  -- infinite recursion

那么我们仍然有f (g 2) = 42 {g 2/x} = 42因为x未使用.我们不必担心是否g 2定义(永远循环).定义展开始终有效.

这实际上使得更简单地推断程序行为.

但是,懒惰有一些缺点.一个主要的一点是,虽然程序的语义(可以说)更简单,但估计程序的性能更难.要评估性能,您必须了解的不仅仅是最终结果:您需要拥有导致该结果的所有中间步骤的模型.特别是在高级代码中,或者当一些聪明的优化开始时,这需要一些关于运行时实际工作的专业知识.

Answer 3

这对于程序的执行顺序是否更难以推理？

可能 - 至少,对于来自程序/ OO范例的人来说.我已经在其他急切评估语言中使用迭代器和函数式编程做了很多,对我来说,懒惰的评估策略并不是学习Haskell的主要问题.(在您决定实际登录之前,您有多少次希望您的Java日志语句甚至无法获取消息的数据？)

考虑Haskell中的所有列表处理,就好像它被编译成基于迭代器的实现一样.如果你在Java中用可能的因素n作为一个这样做Iterator<Integer>,你不想在你找到一个不是1或者一个时就停止n吗？如果是这样,迭代器是无限的也无关紧要!

当你了解它时,执行的顺序并不重要.你真正关心的是:

• 结果的正确性
• 及时终止
• 任何副作用的相对顺序

现在,如果你有一个"纯功能"程序,没有副作用.但是什么时候发生？除了直接数字/字符串运算和元代码(即高阶函数)之外,几乎任何有用的东西都会产生副作用.

幸运的是(或者不幸的是,取决于你问的对象),我们将monad作为Haskell中的设计模式,其目的是(除其他事项外)控制评估的顺序,从而控制副作用.

但即使不了解monad和所有这些东西,它实际上也很容易理解执行顺序和过程语言一样.你只需要习惯它.