Joel Reymont writes:
Where's the solution and what is the repmin problem?
On Jun 19, 2006, at 5:21 PM, Jerzy Karczmarczuk wrote:
Such tricks become your second nature, when you take the solution (lazy) of the "repmin" problem by Richard Bird, you put it under your pillow, and sleep for one week with your head close to it.
Well, the Functionalist True Lazy Church considers this to be a part of the Holy Scriptures... R.S. Bird. Using circular programs to eliminate multiple traversals of data. Acta Informatica, 21, pp. 239--250, 1984. Traverse a binary tree ONCE, and replace all the elements by the minimum of all leaves (i.e., construct a new tree, topologically equivalent, but with all leaf nodes being the minimum value within the original source. A one pass algorithm postpones the binding of an argument until the minimum is found... data Tree a = L a | B (Tree a) (Tree a) rpMin :: (Tree Int, Int) -> (Tree Int, Int) rpMin (L a, m) = (L m, a) rpMin (B l r, m) = let (l', ml) = rpMin (l, m) (r', mr) = rpMin (r, m) in (B l' r', ml `min` mr) replaceMin :: Tree Int -> Tree Int replaceMin t = let (t', m) = rpMin (t, m) in t' Google, your not-so-humble friend will find you some dozen references... For example, Levent Erkök: http://www.cse.ogi.edu/PacSoft/projects/rmb/repMin.html Jerzy Karczmarczuk