CONLIKE

[Roman Leshchinskiy]

On 03/11/2009, at 03:37, Simon Peyton-Jones wrote:

> Roman, Manuel [ccing cvs-ghc for interest]
>
> Consider this:
>
> 	let xs = build g
> 	in map (\y. ...(foldr k z xs)...) ys
>
> The foldr/build rule doesn't fire, because in principle it might  
> take lots of work to construct the list 'xs'.  By doing it outside  
> the 'let' we share all the computation of producing xs across every  
> element of ys.  But in exchange we allocate xs, and retain it.
>
> A common case is when xs started life as [p..q].  For example
>
> 	f x y = length [(a,b) | a <- [1..x], b <- [1..y]]
>
> Then you might reasonably argue that it's cheaper to reconstruct xs  
> for every y, rather than to share it.  By the time we've done a bit  
> of inlining we get
>
> 	let g = \cn. eftIntFB c n p q
>          xs = build g
>      in ...as before...
>
> In short, we'd like to treat (build g) as CONLIKE, *for this  
> particular g*.  Not for all g's.  You can see this by just inlining  
> build in your head to get
> 	xs = g (:) []
> Now if g was CONLIKE we'd be away!

I think you can do this by having two different versions of build: the  
normal one and a CONLIKE one. In enumFromTo you'd use build_conlike  
(for Int, at least) whereas for expensive computations you'd use build  
as before.

> Somehow we'd like to say
> 	
> 	build is CONLIKE if its argument is CONLIKE
>
> Or possibly
>
> 	when trying to decide if (build g) is CONLIKE
> 	inline 'build' and see if the result is CONLIKE
>
>
> I wondered whether you've encountered this anywhere in NDP?  Or  
> generally whether it rings any bells.

I vaguely remember thinking about something like this at some point  
but I think this is getting far too complex. If we really need this,  
I'd much rather implement some form of conditions in rules and write  
something like this:

   forall g | isConlike g . build g = build_conlike g

Roman