Haskell语言的惰性计算特性庞建民1,2,赵荣彩1(11信息工程大学信息工程学院,河南郑州450002;21英国DURHAM大学,Durham,UK,DH13LE)摘要:惰性计算特性是函数式程序设计语言Haskell的重要特征,在开发软件时利用Haskell的惰性计算特性解决了其它语言较难解决的一些问题,但如何在实际编程中充分利用这一特性并不是一件容易的事情。该文详细介绍Haskell的惰性计算特性,阐述如何用这些特性来编写简洁优美的程序。关键词:惰性计算;函数式语言;Haskell;高阶函数;列表内中图分类号:TP311.5文献标识码:A文章编号:1671-0673(2006)01-0063-04OntheFeaturesofLazyEvaluationofHaskellPANGJian-min1,2,ZHAORong-cai1(1.InstituteofInformationEngineering,InformationEngineeringUniversity,Zhengzhou450002,China;2.UniversityofDurham,Durham,UK,DH13LE)Abstract:ThefeaturesoflazyevaluationoffunctionalprogramminglanguageHaskellareveryimportant.Theauthourshavesolvedsomedifficultproblemswhicharehardtodealwithbyotherprogramminglan2guagesindevelopingsoftware.Butitisnoteasytousethesefeaturesinapplicationseffectively.ThispaperintroducesthefeaturesoflazyevaluationofHaskellindetail些开放源代码软件中也包含了用Haskell语言开发的一些工具包。Haskell语言的惰性计算特性对程序的编写影响很大,考虑不周就会陷入死循环本文的重点就是讨论这一特性,并通过实际例子来阐述如何巧妙地利用它。1Haskell语言概述Haskell语言是一种基于λ-演算模型的“多态类型纯函数式惰性语言”,它以著名逻辑学家HaskellB.Curry的名字命名。其第一版Haskell110诞生于1990年,目前发行的版本称为Haskell98。像大多数函数式语言一样,Haskell是一个强类型语言,它既支持由基本类型构成的单态类型,如Int和Char,也支持像记录和联合这样的用户自定义的结构类型,并且它还支持多态类型。Haskell语言支持惰性计算,并且是无副作用的。目前国外已经2惰性计算特性在我们处理数学计算问题时,当一个子表达式的值不需要求出就能得到整个表达式的值的时候,我们自然不去求该子表达式的值。但在程序设计语言中,要想达到上述灵活性,就有一定的难度,这就需要用到惰性计算的概念和技术。惰性计算是指只有在确实需要时才求值的一收稿日期:2005-10-10基金项目:欧盟项目TYPES(typesproject29001)作者简介:庞建民(1964-),男,河北沧州人,信息工程大学教授,主要研究方向为计算机辅助推理与软件理论。E-mail:jianminpang@种计算理念。Haskell之所以被称作“惰性语言”,是由于除非迫不得已(即计算结果将被使用),否则它不对表达式进行求值。和“惰性语言”相反,大多数通用编程语言(C、C++、Java、甚至函数式语言ML)的求值是严格(strict)的。一个严格的语言是说它的每一个表达式都需要求值,而不论是否这个表达式在实际中确实需要求值(这么说也不完全准确,因为严格语言的优化编译器经常做“无用代码消去(deadcodeelimination)”工作,这个过程可以消去代码中无用的表达式。但这并不是语言本身强制要求的,而是优化编译器的设计者自觉的行为)。首先,让我们比较下列表达式在Haskell语言和ML语言中的求值情况。在Haskell中,使用惰性计算技术,表达式程变得简洁。许多优美的符合人类思维习惯的想法可以被非常自然地表述出来。而其它非函数式程序设计语言则几乎无法做到这一点。甚至在强制性语言中,我们的直觉也告诉我们不能这样做。3惰性计算特性的应用在Haskell语言中,人类的思维习惯可以通过惰性计算特性的应用得以体现。下面几个小节反映了惰性计算特性的一些应用方面。311表示无穷的数据结构在Haskell中,可以定义一个无穷的数据结构,只要你只使用其中一部分数据而不使用无穷多个数据,就不会有问题。例如,利用类强制性语言的伪代码,可以象下面这样创建一个每个位置上都是8的无穷的列表。ListeightList(){Listcurrent=newList();current.value=8;current.next=eightList();returncurrent;}让我们来看看上述这段伪代码。它首先创建了一个新的列表,设置它的节点值为8,然后,递归地调用它自己再创建其余的节点。很显然,这种写法在C或者Java语言中...