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

[John van Groningen]

On 26-7-2013 11:54, zuurb078 at planet.nl wrote:
> 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).

Yes.

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

Yes, for example:

undef_int :: Int
undef_int = undef

Start = isEmpty [undef_int..]

To prevent the large 1+1+1+1.. lazy computation, you could use:

gen_list n = gen_int_list 0 n
where
	gen_int_list :: !Int Int -> [Int]
	gen_int_list a n
		= [n+a : gen_int_list (a+1) n]

Kind regards,

John van Groningen

>
> -----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
>
>
>
>
>
>
>
>
> _______________________________________________
> clean-list mailing list
> clean-list at science.ru.nl
> http://mailman.science.ru.nl/mailman/listinfo/clean-list