lazy-eval

什么是惰性求值

惰性在函数式编程语言中很常见，他的通俗解释就是一个变量或者表达式，不到必要的时候不会被 eval。比如函数在传递参数的时候，参数的值可以不确定。

这种方式叫做 call-by-name，首先很明显这可能会造成一部分 performance 差异，如果一个表达式没有用到，那么计算出其结果是毫无意义的。而惰性求值是 memoized 的 call-by-name，叫做 call-by-need。
从技术实现上来说，一个表达式在计算其结果之前其状态是 Deferred 或者 Delayed 的，在计算之后将其结果存储下来并修改状态为 Value，之后再取就没有必要重新去计算。用一些 OCaml 代码来说明：

# let v = lazy (print_string "performing lazy computation\n"; sqrt 16.);;
val v : float lazy_t = <lazy>

# Lazy.force v;;
performing lazy computation

- : float = 4.
# Lazy.force v;; - : float = 4.

关键字 lazy 表示延迟计算这个表达式，Lazy.force 表示求值。可以看到第一次 force 的时候会打印出 performing…信息，后面的 force 就直接返回了 value。

为了更好的理解这个概念，我们可以实现一把 Lazy。首先定义一个 lazy_state:

# type 'a lazy_state =
| Delayed of (unit -> 'a)
| Value of 'a
| Exn of exn
;;

# let create_lazy f = ref (Delayed f);;

这个 lazy_state 有三种状态，第一种就是 dealyed，’a 表示任何类型的 value。Value 表示被 eval 过了，并且保存下来他的值。Exn 表示错误或者异常的状态。那么 create_lazy 就表示创建一个 lazy_expression，这里的参数 f 可以是任何类型的函数 (函数的参数类型和返回类型都可以不确定)，ref 是 OCaml 里面的类似指针的概念。

上面例子就可以这样来写了：

# let v = create_lazy (print_string "performing lazy computation\n"; sqrt 16.);;

然后实现核心的 force:

# let force v = match !v with
    | Value x -> x        (* 如果已经求值就直接返回 value *)
    | Exn e -> raise e    (* 如果发生错误，raise 错误*)
    | Delayed f ->
        try
            let x = f () in  (* 如果还未求值，eval 保存下来的 f *)
            v := Value x;    (* 并把结果保存下来 *)
            x
        with exn ->
            v := Exn exn;    (* 如果发生错误，保存下来 *)
    raise exn
    ;;

这里的！v 就是取这个引用里面的值 (类比 C 语言里面的*pointer)。然后 pattern match 这个 lazy_state，注释里面写了每一行的操作。这里的代码很简短，最核心的意思是我们能把一个函数或者代码块保存下来，在真正需要的时候去运行这个代码块。在函数式编程里面这很常见，函数和变量一样可以自由传递。虽然看起来好不起眼，不过这会给编程带来一些深刻的影响。

Memoization

通过上面对 laziness 的解释，我们可以发现这个概念的核心思想类似算法设计里面的 memoization，这样在计算过程中把重复计算的过程省略掉。比如这段代码有些好玩：

let memoize f =
    let table = Hashtbl.Poly.create ()
    in (fun x ->
      match Hashtbl.find table x with
      | Some y -> y
      | None ->
        let y = f x in
        Hashtbl.add_exn table ~key:x ~data:y;
        y
     );;

这个函数接收任何类型的函数 f，他会像一个 wrapper 一样给你包装一下：给你一个 table 用来存储这个函数的结果，键值是你的参数 x，如果发现参数是 x 的结果还没计算的时候，把结果算出来并存储在 table 里面。
这里我们又能看到函数式编程带来的好处，f 是任何类型的函数 (这里暂且还没处理递归)，这类问题在算法设计里面挺多的比如 fibnacci，edit-distance。

在递归情况下如何处理可以看看这，这是我看过的排版最好的技术类博客Type OCaml:
Recursive Memoize & Untying the Recursive Knot

Stream

有了 lazy 的概念之后，我们可以在编程里面表示一些看起来很数学的概念，比如一个表示所有整数的流：

type 'a stream_t = Nil | Cons of 'a * (unit -> 'a stream_t)

let rec from i = Cons (i, fun() -> from (i+1))

let hd = function
    | Nil -> failwith "hd"
    | Cons (v, _) -> v

let tl = function
    | Nil -> failwith "tl"
    | Cons (_, g) -> g()

let rec take n = function
    | Nil -> []
    | Cons (_, _)  when n = 0 -> []
    | Cons (hd, g) -> hd::take (n-1) (g())

Cons 是把两个元素组成链表，递归函数 from 做的事情就是把 i 和一个匿名函数 fun() -> from(i+1) 链起来，当然匿名函数又在做类似的事情。
那么 (from 1) 就可以表示从 1 开始的所有整数了，hd 是取一个流的头部，tl 是取流的尾部 (除头部剩下的)，take 是从一个流里面取前 n 个元素。这可是非常的方便，还有更方便的：

let rec filter f = function
    | Nil -> Nil
    | Cons (hd, g) ->
        if f hd then Cons (hd, fun() -> filter f (g()))
        else filter f (g())

我们虽然只知道有这么一个流，但还是可以加一个筛选条件给他，filter 函数接收筛选函数 f 和一个流，返回的结果就是被筛选后的流！

(* delete multiples of p from a stream *)
let sift p = filter (fun n -> n mod p <> 0)

(* sieve of Eratosthenes *)
let rec sieve = function
    | Nil -> Nil
    | Cons (p, g) ->
        let next = sift p (g()) in
        Cons (p, fun () -> sieve next)

(* primes *)
let primes = sieve (from 2)

所有素数就可以这么来写了，有了这个流之后要取多少就取多少。

其他

Haskell 是纯函数式纯 Lazy 的实现，OCaml 有 imperative 的部分，而且运行时不是 Lazy 的。相对来说我更喜欢 OCaml 的语法以及设计原则，FP 有其好处，但 imperative programming 也有其益处。Lazy 有其好处，但还是在用户明确需要的时候能提供就好。

部分代码引用Real World OCaml