Lazy minimum

[Dave Bayer]

On Nov 20, 2008, at 1:27 AM, David Menendez wrote:

> There are also possible space issues, since "min a b" will end up re- 
> creating much of "a" or "b" if they share a large common prefix.

Thanks! I had put off writing the version I needed until seeing your  
code, which inspired me:

> Compute the least list in a list of equal length lazy lists
>
>   least :: forall a. Ord a => [[a]] -> [a]
>
>   least ((x : xs) : xss) = w : least wss
>     where
>     (w, wss) = foldl' f (x, [xs]) xss
>
>     f :: (a, [[a]]) -> [a] -> (a, [[a]])
>     f v@(y, yss) (z : zs) =
>       case compare y z of
>         LT -> v
>         EQ -> (y, zs : yss)
>         GT -> (z, [zs])
>     f v _ = v
>
>   least _ = []


In my applications, there are usually many instances of the minimum,  
so peeling off a reference copy isn't all that wasteful. I just want  
to avoid evaluating everything else.

So to summarize the responses, there's no GHC language support for  
introspecting lazy structures, allowing one to write a generic bounded  
compare that only evaluates lazy structures to a specified depth. One  
can however write a class, and solve this problem type-by-type with a  
common interface.

I can see how providing language support for this could be  
controversial. Functions would remain referentially transparent within  
a given compilation, but their values would depend non-portably on the  
compiler.

(I use a "code is indented, comments are flush" literate preprocessor (http://hackage.haskell.org/trac/ghc/ticket/2776 
) so I don't have to look at punctuation for either code or comments;  
syntax coloring makes it obvious which is which. The 1980's email  
quote symbols > in the default literate Haskell reminds me of being  
introduced to an IBM 360 in college, and being told I was working with  
virtual card images. I gasped. I remember punched cards, and it isn't  
an experience I want to relive. I also remember 1980's email, so my  
first reaction to literate Haskell was "You've got to be kidding!"  
Ahh, but better to propose a fix than to gripe.)