2018年4月21日星期六

Lazy computation在实际应用中的妙用

举一个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/

4 条评论:

  1. lazy computation是不是惰性求值?但是where那里没有看得很懂......
    ----以下是来自夏津一中晚辈的问候----
    杨志飞学长的博客终于更新了!而且这次不仅换了主题还一更两篇博客!可喜可贺啊!
    连名字都换了,搞得我有点懵......
    自从我NOIP出成绩以后,我们基本没怎么联系过吧(省二没脸...)。
    不过现在我也有博客啦:www.xjdesyxx.top
    中间发生了好多事情.就不详细说了。

    回复删除
  2. 《算法竞赛入门经典》全书例题习题代码 什么都没有

    回复删除
  3. 博客还会更新吗...

    回复删除