Laziness and Evaluation Model of Haskell

The two core concepts in Haskell is

• Purity, meaning that same input always gives same output.
• Laziness. Expressions are not evaluated unless necessary.

Thunk

A thunk is a value that is yet to be evaluated. A lazy run-time system does not evaluate a thunk unless it has to.

In Haskell, expressions are translated into graphs. Then, a Spineless Tagless G-machine reduces it to chuck out any unneeded (thus unevaluated) thunks.

Weak Head Normal Form

Haskell evaluate 的方式是 outside-in，先代入函数定义，再逐步替换参数．更具体地说，Haskell 尝试对当前表达式进行 pattern matching，一旦可以匹配上，就进行替换．只有以下可以被 pattern match（也被称为 weak head normal form WHNF）

• 常数
• 最外层有一个构造函数的表达式，e.g. Just x, [], (:)
• 函数，e.g. \x -> ...

Sharing

Haskell 对表达式会构建计算图 DAG，如果函数体中需要反复用到某一个表达式的结果，那么 Haskell 只会重复计算这个表达式一次，并用有向边表示“其他地方使用计算结果”

要想参数共享计算结果，他们必须是 same named，如：

• function parameter 中定义
• let in 里定义
• where 里定义

1
2
3
4
5
6
7
8
9

f :: Int -> Int
f i = if i > 10 then 10 else i

                  _______shared________
                 |                     |
f (1+1) ==> if (1+1)>10 then 10 else (1+1)
        ==> if 2>10 then 10 else 2
        ==> if False then 10 else 2
        ==> 2

1
2
3
4
5
6
7
8
9
10

g :: Int -> Int -> Int
g i j = if i>10 then 10 else j

                        ______no sharing_____
                       |                     |
g (1+1) (1+1) ==> if (1+1)>10 then 10 else (1+1)
              ==> if 2>10 then 10 else (1+1)
              ==> if False then 10 else (1+1)
              ==> (1+1)
              ==> 2

Strictness

先回顾一下 foldl 和 foldr

1
2
3
4
5
6
7

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f y []     = y
foldr f y (x:xs) = f x (foldr f y xs)

从定义可以看出，foldr 更适合 laziness/short-circuiting operations，而 foldl 却需要遍历整个列表才能产出一个 WHNF 值．

foldl'

那么为什么我们还需要 foldl 呢？我们考察其变种 foldl'，它强制其第二个参数 f z x 先完成计算再继续．我们发现 foldl' 由于所有计算都是直接完成的，没有 space leak．

foldl' 在 Data.List Module 里

要想实现泛型版本的 foldl'，我们需要一个内置函数 seq，seq a b 返回 b 的值，但是会先强制将 a 转为 WHNF 形式．