[clean-list] hd (drop 1000000 [1..]) heapFull

[zuurb078 at planet.nl]

OK, the problem is not that 1000000 dropped elements would be lingering in the heap.
The problem is that element 1000001 is not actually evaluated until it is really realy needed by
Start = hd ..
Until then, element 1000001 is a huge thunk 1+1+1+1... (consisting of 1000001 numbers and 1000000 references to the +-operator).

Say we would have a version of gen_list that would be strict in its argument.
Could we write a program that would not terminate, while a version with a lazy gen_list would?


-----Oorspronkelijk bericht-----
Van: clean-list-bounces at science.ru.nl namens zuurb078 at planet.nl
Verzonden: ma 22-7-2013 17:11
Aan: Clean List
Onderwerp: Re: [clean-list] hd (drop 1000000 [1..])  heapFull
 
So is this desired behaviour, in the context of hd?
 

________________________________



On 19-7-2013 22:10, Pieter Koopman wrote:
> Hi Erik,
>
> there seems to be a problem with the generator.
>
> Start = hd (drop n [1..n+10]) where n = 1000000
>
> works fine. Hopefully John can explain this.

[1..] generates a list in the following way:

let
        gen_list n = [n : gen_list (n+1)]
in
        gen_list 1

Because gen_list is not strict in argument n,
a thunk is created for the expression (n+1) at runtime.
The first time this creates a thunk t0 with 1+1,
the next time a thunk t1 with t0+1, then t2 with
t1+1, ..
So after 1000000 elements, the heap contains 1000000
thunks.

The arguments of the function generated for [1..n+10] are strict,
because 1 is compared with n+10, so no increment thunks
are created.

> On 7/19/13 4:41 PM, zuurb078 at planet.nl wrote:
>> Re: [clean-list] Matrix operations
>> Start = hd (drop 1000000 [1..])
>> with standard heap (2M) leads to a heapfull message; not when I only
>> drop 1000.
>> I had expected the garbage collector to kick in so this would
>> effectively run in constant space
>> Any ideas?
>>
>>
>> _______________________________________________
>> clean-list mailing list
>> clean-list at science.ru.nl
>> http://mailman.science.ru.nl/mailman/listinfo/clean-list
>
>
>
>
> _______________________________________________
> clean-list mailing list
> clean-list at science.ru.nl
> http://mailman.science.ru.nl/mailman/listinfo/clean-list





-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.science.ru.nl/pipermail/clean-list/attachments/20130726/3429ffd0/attachment.html>