# [Haskell-cafe] Computing lazy and strict list operations at the same time

jerzy.karczmarczuk at info.unicaen.fr jerzy.karczmarczuk at info.unicaen.fr
Mon Jun 19 13:54:16 EDT 2006

```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'