CONLIKE

Roman Leshchinskiy rl at cse.unsw.edu.au
Mon Nov 2 17:58:58 EST 2009

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