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

[jerzy.karczmarczuk at info.unicaen.fr]

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