2018年4月21日星期六

Lazy computation在实际应用中的妙用

万物学徒 写于 四月 21, 2018
举一个circular programming的简单例子：遍历二叉树。



题目描述

题目要求很简单：
用一趟遍历（包括但不限于递归），实现将二叉树中所有结点的值全部改为该二叉树中所有结点值的最小值。

传统的方法是先用一趟遍历获取最小值，再用一趟遍历将所有node的值改为这个最小值。我们这次要求完成目标，in just one pass。


定义二叉树的结构为（Haskell表示）：
data Tree = Leaf Int | Branch Int Tree Tree

样例输入输出
[Input]
Branch 7 (Branch 4 (Leaf 5) (Leaf 3)) (Leaf (-99))
[Output]
Branch (-99) (Branch (-99) (Leaf (-99)) (Leaf (-99))) (Leaf (-99))
[Input]
Branch (-2) (Branch 7 (Leaf 3) (Leaf 5)) (Branch 2 (Leaf 4) (Branch 8 (Leaf 9) (Leaf 6)))
[Output]
Branch (-2) (Branch (-2) (Leaf (-2)) (Leaf (-2))) (Branch (-2) (Leaf (-2)) (Branch (-2) (Leaf (-2)) (Leaf (-2))))

解答
repMin' (Leaf n, r) = (n, Leaf r)
repMin' (Branch v a b, r) = (min v $ min min1 min2, Branch r a' b')
  where (min1, a') = repMin' (a, r)
        (min2, b') = repMin' (b, r)

repMin t = newTree where
  (min, newTree) = repMin' (t, min)

repMin函数的神奇之处在于把一个返回值当成了传入函数的参数，这种input和output相互依赖的程序能够跑通的关键就在于lazy evaluation。拿个样例自己试一下整个递归过程，会很有助于理解。

参考资料：
Circular programming
techo.io/topic/38/