September 16, 2013

RepMin问题出自Richard Bird的一篇论文Using Circular Programs to Eliminate Multiple Traversals of Data，穷逼买不起论文，但是还是可以从各种渠道了解到其中的内容，其中的重点应该是Circular Programs，不过这里只记录一下RepMin问题。

先简单地复述一下RepMin问题：给定一个树，把其中全部节点的值替换成树中最小的值。

data Tree = Empty | Node Int Tree Tree

repMin:: Tree -> Tree
repMin = undefined

解决

这问题怎么看好像都要把整棵树遍历两次：

求最小值m
把全部节点的直替换成m

treeMin Empty = maxBound
treeMin (Node x l r) = minimum [x, treeMin l, treeMin r]

treeMap f Empty = Empty
treeMap f (Node x l r) = Node (f x) (treeMap f l) (treeMap f r)

repMin2 t = let m = treeMin t in treeMap (const m) t

Bird就想出一种只要遍历一次的方法。

首先，我们先考虑一个简单点问题：求树中的最小的值m，同时把全部值换成n。这~~真的是~~看起来是可以在一次遍历中完成的：

repMin' :: Int -> Tree -> (Int, Tree)
repMin' n Empty = (maxBound, Empty)
repMin' n (Node x l r) =
    let (ml, tl) = repMin' n l
        (mr, tr) = repMin' n r
    in (minimum [ml, mr, x], Node n tl tr)

这和原来的问题有什么联系呢？首先我们通过repMin' n可以求得最小值m，还可以把节点都替换成另一个值n。如果我们通过循环引用令m = n会变成怎样呢？

本来是这样的：

let (m, t') = repMin' n tree in t'

然后把m也设为n：

let (n, t') = repMin' n tree in t'

然后你就发现结果的t'刚好是我们想要的结果，也就是说repMin可以这样实现：

repMin t = let (m, t') = repMin' m t in t'

这从语义上理解是可以的，从操作上理解就比较复杂。

repMin遍历树的时候把节点的值都换成m(每个节点都分享同一个m)，而m是遍历过程建立的一个求最小值的表达式(形如minimum [minimum [minimum[...], ...], minimum [...], ...]，就像建了另一棵树)。

一次遍历？

首先，repMin'是只用遍历一次的，然后我们在Hugs或者GHC里比较一下repMin' 0，repMin2和repMin需要规约的次数和占用内存，就可以大概知道repMin是不是一次遍历。

我用下面这个函数来生成树：

mkTree n
    | n < 0 = Empty
    | otherwise = Node n (mkTree (n - 1)) (mkTree (n - 2))

然后对比规约的次数和使用内存量，看起来很神奇的repMin比遍历两次的repMin2要差一点，比repMin'好一点。repMin虽然对树是一次遍历，但是对m求值的时候,再遍历了另一棵表达式树(repMin'存在同样的问题)，所以和同样是惰性求值的repMin2想比没有任何优势。