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

Google, your not-so-humble friend will find you some dozen references...
For example, Levent Erkök:

Jerzy Karczmarczuk 

More information about the Haskell-Cafe mailing list