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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
