Memory usage

Dusan Kolar
Thu, 23 Nov 2000 16:00:52 +0100


  working on a small utility for de/compression of special files
using special algorithm (useless in other cases and not important
for the problem) I've encountered I cannot decompress even small
files because I always run out of the memory.

  After some time I've found the problem. It can be simplified
to the following function (computing nothing reasonable):

tst l [] = id
tst l (x:xs) = if null l then ((++) [x]) . (tst (l++[x]) xs) 
               else if null (tail l) then ((++) [x,last l]) . (tst (tail
l++[last l]++[x]) xs)
               else ((++) [x,last l]) . (tst (tail (tail l)++[last l]++[x]) xs)

Trying to run it in hugs (default settings) this way:

tst [] [1..20000] []

the program stops writing almost all the lines and running out of memory.

Nevertheless, just a minor change to the function ([last l] replaced with [x]):

tst' l [] = id
tst' l (x:xs) = if null l then ((++) [x]) . (tst' (l++[x]) xs) 
               else if null (tail l) then ((++) [x,last l]) . (tst' (tail
l++[x]) xs)
               else ((++) [x,last l]) . (tst' (tail (tail l)++[x]++[x]) xs)tst'
l [] = id

and we can run the:

tst' [] [1..1000000] []

easily, till it writes out the complete list.

Could you point me somewhere to see where is the error and how
it can be solved?


    Dusan Kolar