这个Haskell的例子是否有效地证明了懒惰



我是Haskell的新手,我正在为我的编程语言类写一篇关于它的论文。我想用一些示例代码来展示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]

感谢您的时间和帮助!

您在这里对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]

你可以看到只有五个数字被加倍,因为只有五个结果被要求;即使给予CCD_ 3的列表具有10个条目。

注意,trace通常不是一个监控"执行流"的好工具,它只是一个允许"查看"局部变量以查看某个函数中发生了什么的破解。

无限流总是一个很好的例子。如果没有特殊的构造,你就无法在其他语言中获得它们——但在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

你可以通过一些人为的例子来证明哈斯克尔的懒惰。但我认为,展示懒惰如何帮助您开发出比其他语言模块化程度高得多的常见问题的解决方案要好得多。

简短的回答是"否"。leftaroundabout在他的回答中很好地解释了这一点。

我的建议是:

  1. 阅读并理解懒惰评估的定义
  2. 编写一个函数,其中一个参数可能会出现分歧,例如在您喜欢的严格(非懒惰)语言(C、python、Java)中不能工作。例如,sumIfFirstArgIsNonZero(x,y),如果x!=0,否则为0
  3. 为了获得奖励,请定义自己的函数ifThenElse,该函数不使用Haskell内置的if-then-else语法,并解释为什么用惰性语言编写新的控制流结构很容易

这应该比试图绕过无限的数据流或打结技巧更容易。

懒惰的主要原因是不计算不需要的值——因此,为了证明这一点,您必须显示而不是正在评估的内容。你的例子并不是证明懒惰的最佳例子,因为所有的值最终都是计算出来的。

这里有一个小例子,作为起点:

someValueThatNeverTerminates = undefined -- for example, a divide-by-zero error
main = do (greeting, _) = ("Hello terminating world!", someValueThatNeverTerminates)
putStrLn greeting

这会立即向你问好——如果它不懒惰的话,整件事就会半途而废。

最新更新