[Haskell-cafe] what does @ mean?.....

[Jules Bean]

Luke Palmer wrote:
> On Dec 28, 2007 9:35 AM, Jules Bean <jules at jellybean.co.uk> wrote:
>> In particular, adding sharing can stop something being GCed, which can
>> convert an algorithm which runs in linear time and constant space to one
>> which runs in linear space (and therefore, perhaps, quadratic time).
> 
> I've heard of this before, but can you give an example?

Sure:

foo (length (build_big_list 1 2 3)) (build_big_list 1 2 3)

Here, "foo" is a function which operates on a list, but needs to know 
the length of the list for some reason.

As written, build_big_list is called twice. This is potentially a waste 
of time, but it *does* mean that if the big list is very  very big 
(larger than available memory) but build_big_list is a good producer, it 
can be produced and GCed in constant space - as long as length is a good 
consumer (which it is) and as long as foo is (can't tell without seeing 
the definition, obviously!)

So, you can do a two-pass algorithm in two-passes, but in constant space.

Now, if we automatically share those two, we get something like this:

let l = build_big_list 1 2 3 in foo (length l) l

which *looks* like an optimisation, but the shared 'l' will be kept 
around. The length will be calculated first (assuming foo uses the 
length, that is) and then the entire list kept in memory while foo 
processes it.

Of course, it's hard to see this kind of problem with the simple x@(Just 
y) case we were talking about, but if your function calls itself 
recursively then it can.

Jules