这个Haskell示例是否有效地展示了懒惰？

Question

我是Haskell的新手,我正在为我的Programming Languages课写一篇论文.我想用一些示例代码演示Haskell的懒惰,但我不确定我所看到的是否实际上是懒惰.

doubleMe xs = [x*2 | x <- xs]

在ghci:

let xs = [1..10]
import Debug.Trace
trace (show lst) doubleMe (trace (show lst) doubleMe (trace (show lst) doubleMe(lst)))

输出:

[1,2,3,4,5,6,7,8,9,10]
[1,2,3,4,5,6,7,8,9,10]
[1,2,3,4,5,6,7,8,9,10]
[8,16,24,32,40,48,56,64,72,80]

感谢您的时间和帮助!

Answer 1

您在trace这里的使用并不是特别有见地,或者实际上根本没有.您所做的就是在评估中的四个不同点打印出相同的列表,这不会告诉您有关程序实际状态的任何信息.这里实际发生的是trace在计算甚至开始之前每次加倍步骤(当结果列表被请求为弱头正常形式时).这与完全严格评估的语言几乎相同.

要看到一些懒惰,你可以做点什么

Prelude Debug.Trace> let doubleLsTracing xs = [trace("{Now doubling "++show x++"}")$ x*2 | x<-xs]
Prelude Debug.Trace> take 5 $ doubleLsTracing [1 .. 10]
{Now doubling 1}
{Now doubling 2}
{Now doubling 3}
{Now doubling 4}
{Now doubling 5}
[2,4,6,8,10]

你可以看到只有五个数字加倍,因为只要求五个结果; 即使doubleLsTracing给出的列表有10个条目.

请注意,这trace通常不是监视"执行流程"的好工具,它只是一个允许"查看"局部变量以查看某些功能中发生了什么的黑客.

Answer 2

无限的流总是一个很好的例子.没有特殊的结构,你无法用其他语言获得它们 - 但在Haskell中它们非常自然.

一个例子是斐波那契流:

fib = 0 : 1 : zipWith (+) fib (tail fib)

take 10 fib => [0,1,1,2,3,5,8,13,21,34]

另一个是使用试分法获得素数流:

primes = sieve [2..]
    where sieve (x:xs) = x : filter (not . (== 0) . (`mod` x)) (sieve xs)

take 10 primes => [2,3,5,7,11,13,17,19,23,29]

此外,在Haskell中实现回溯非常简单,使您能够根据需要懒洋洋地获取解决方案列表:

http://rosettacode.org/wiki/N-queens_problem#Haskell

一个更复杂的例子,显示了如何实现min是在这里找到的:

懒惰的评估和时间复杂性

它基本上显示了如何使用Haskell的懒惰你可以获得一个非常优雅的minimum函数定义(在元素列表中找到最小值):

minimum = head . sort

你可以用人为的例子来证明Haskell的懒惰.但我认为,更好地展示懒惰如何帮助您为常见问题开发解决方案,这些问题比其他语言具有更大的模块性.