[Haskell-cafe] multiple computations, same input

[Jan-Willem Maessen]

On Mar 28, 2006, at 1:02 AM, Tomasz Zielonka wrote:

> On Mon, Mar 27, 2006 at 03:10:18PM -0800, Greg Fitzgerald wrote:
>>> hold a part of the data in memory while you show the first one,
>>
>> Here would be a better example then.
>>
>>     f lst = show (sum (filter (> 1) lst), sum (filter (> 2) lst))
>>
>> It ought to be *possible* to compute both operations without  
>> holding onto
>> any of the list elements.
>
> I wonder if it would be possible to remove the space-leak by  
> running both
> branches concurrently, and scheduling threads in a way that would
> minimise the space-leak. I proposed this before
>
>   http://www.haskell.org/pipermail/haskell-cafe/2005-December/ 
> 013428.html
>
> I would like to hear opinions from some compiler gurus.

This is possible in principle with something like resource-bounded  
eagerness, but it's not at all easy.  The problem is this: when lst  
gets big, you need to identify who's hanging on to it, and figure out  
that they are actually planning to consume it and come up with  
something smaller as a result.  This is all pretty heavyweight---not  
hard in principle, but hard enough in practice that it may not be  
worth the investment.

That said, there's a transformation that goes something like this:

a = foldr f z xs         ==>           (a,b) = foldr (f `cross` g)  
(z,y) xs
b = foldr g y xs

This could in principle at least pluck the lowest-hanging fruit (sum,  
filter, etc.).
However it runs into some significant problems:
- Only works with folds
- Has some problems with bottoms, if I recall rightly
- Not expressible using something like RULES;
    requires a special transformation in the compiler.
- It is often a pessimization.

That last point is a killer.

>
> Best regards
> Tomasz
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe