Luke Palmer wrote:

On Dec 28, 2007 9:35 AM, Jules Bean 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