<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<META NAME="Generator" CONTENT="MS Exchange Server version 6.5.7654.12">
<TITLE>RE: [clean-list] hd (drop 1000000 [1..]) heapFull</TITLE>
</HEAD>
<BODY>
<!-- Converted from text/plain format -->
<P><FONT SIZE=2>OK, the problem is not that 1000000 dropped elements would be lingering in the heap.<BR>
The problem is that element 1000001 is not actually evaluated until it is really realy needed by<BR>
Start = hd ..<BR>
Until then, element 1000001 is a huge thunk 1+1+1+1... (consisting of 1000001 numbers and 1000000 references to the +-operator).<BR>
<BR>
Say we would have a version of gen_list that would be strict in its argument.<BR>
Could we write a program that would not terminate, while a version with a lazy gen_list would?<BR>
<BR>
<BR>
-----Oorspronkelijk bericht-----<BR>
Van: clean-list-bounces@science.ru.nl namens zuurb078@planet.nl<BR>
Verzonden: ma 22-7-2013 17:11<BR>
Aan: Clean List<BR>
Onderwerp: Re: [clean-list] hd (drop 1000000 [1..]) heapFull<BR>
<BR>
So is this desired behaviour, in the context of hd?<BR>
<BR>
<BR>
________________________________<BR>
<BR>
<BR>
<BR>
On 19-7-2013 22:10, Pieter Koopman wrote:<BR>
> Hi Erik,<BR>
><BR>
> there seems to be a problem with the generator.<BR>
><BR>
> Start = hd (drop n [1..n+10]) where n = 1000000<BR>
><BR>
> works fine. Hopefully John can explain this.<BR>
<BR>
[1..] generates a list in the following way:<BR>
<BR>
let<BR>
gen_list n = [n : gen_list (n+1)]<BR>
in<BR>
gen_list 1<BR>
<BR>
Because gen_list is not strict in argument n,<BR>
a thunk is created for the expression (n+1) at runtime.<BR>
The first time this creates a thunk t0 with 1+1,<BR>
the next time a thunk t1 with t0+1, then t2 with<BR>
t1+1, ..<BR>
So after 1000000 elements, the heap contains 1000000<BR>
thunks.<BR>
<BR>
The arguments of the function generated for [1..n+10] are strict,<BR>
because 1 is compared with n+10, so no increment thunks<BR>
are created.<BR>
<BR>
> On 7/19/13 4:41 PM, zuurb078@planet.nl wrote:<BR>
>> Re: [clean-list] Matrix operations<BR>
>> Start = hd (drop 1000000 [1..])<BR>
>> with standard heap (2M) leads to a heapfull message; not when I only<BR>
>> drop 1000.<BR>
>> I had expected the garbage collector to kick in so this would<BR>
>> effectively run in constant space<BR>
>> Any ideas?<BR>
>><BR>
>><BR>
>> _______________________________________________<BR>
>> clean-list mailing list<BR>
>> clean-list@science.ru.nl<BR>
>> <A HREF="http://mailman.science.ru.nl/mailman/listinfo/clean-list">http://mailman.science.ru.nl/mailman/listinfo/clean-list</A><BR>
><BR>
><BR>
><BR>
><BR>
> _______________________________________________<BR>
> clean-list mailing list<BR>
> clean-list@science.ru.nl<BR>
> <A HREF="http://mailman.science.ru.nl/mailman/listinfo/clean-list">http://mailman.science.ru.nl/mailman/listinfo/clean-list</A><BR>
<BR>
<BR>
<BR>
<BR>
<BR>
</FONT>
</P>
</BODY>
</HTML>