文档介绍：惰性计算
什么是惰性计算
惰性计算在模块设计中的作用
阅读第十七章
1
惰性计算Lazy Evaluation
Haskell的主要计算是函数应用: 将函数f 应用于参数 a1, …, ak时, 将它们代入f定义等式右边相应的变量.
Haskell 使用惰性计算:
函数的参数只有在需要计算时才被计算;
一个参数不必完全计算,只有需要的部分才被计算;
一个参数最多被计算一次。
2
例
定义函数
g x y = x + 12
则 g (9-3) (g (34 3)) (9-3) +12 6+12 18
另一个例子:
switch :: Int -> a -> a - >a
switch n x y
| n >0 = x
| otherwise = y
(g 34 3) 不需要计算
当 n>0时,不需要计算 y
当 n <= 0时,x不需要计算
3
例
定义函数
h x = x + x
则
h (9-3) (9-3)+(9-3) 6+6 12
其中(9-3) 只需要计算一次。
4
计算规则
函数的一般定义
f p1 p2 … pk
|g1 = e1
…
| otherwise = er
where
v1 a11 …= r1
f q1 q2 … q k = …
计算 f a1 … ak 包含下列三方面:
5
计算–模式匹配
需要计算输入参数至匹配定义中的某个模式,从而决定使用那个等式。例如,
f :: [Int] -> [Int] -> Int
f [] xs = 0
f (x:xs) [] = 0
f (x:xs) (y:ys) = x + y
计算 f [1..3] [1..3] 过程
f [1..3] [1..3] f (1:[2..]) [1..3] f (1:[2..3]) (1:[2..3]) 1+1
6
计算–守卫
假设输入匹配第一个等式,下一步是依次计算条件p1 至 pk, 直至一个条件的值是 True, 然后使用相应的式子作为输出值
f :: Int -> Int -> Int -> Int
f m n p
| m >= n && m >= p = m
| n >= m && n >= p = n
| otherwise = p
f (2+3) (4-1) (3+9)
?? (2+3)>=(4-1) && (2+3) >=(3+9)
… False
?? 3>= 5 && 3 >= 12
False
?? Otherwise
True
7
计算–局部定义
由 where 引入的局部定义只有在需要的时候被计算,而且最多计算一次。例如
f :: Int -> Int -> Int
f m n
| notNil xs = front xs
| otherwise = n
where xs = [m..n]
front (x:y:zs) = x+y
front [x] = x
f 3 5 7
xs 只需计算一次
f 5 3 3
front 不需计算
8
计算次序
当计算存在次序选择时
计算由外至内进行,
例如 f1 e1 (f2 e2 e3), 先计算f1的函数应用。
否则,计算由左至右
例如 f1 e1 e2 + f2 e2 e3, 先计算f1 e1 e2, 后计算 f2 e2 e3.
9
函数是非严格的
Haskell是一个惰性语言。惰性又称为非严格的(non-strict) 。
一个函数称为严格的,如果当它作用于一个非终止的表达式时,计算也不能终止。
Haskell 函数是非严格的。这个特性的优点是:
计算代价大的值可以作为参数传给函数,不需要担心不必要的计算会发生。例如,一个参数可以是无穷的数据结构,我们无需担心内存问题。
更重要的是,惰性计算提供了一种模块程序设计方法,它使得一个问题可以用几个模块解决,并用惰性机制将这些模块粘合起来。
10