[Haskell-cafe] Please help me spot where space leak occur.

[Olexander Kozlov]

Jason, thank you for your help. The hint for using -s option is very
valuable.

It is good to see people answering questions about Haskell here on
haskell-cafe.
This is really matter. I hope I will be helpfull some day too :)

As for the question I didn't mention in my psot that Fn can be of arbitrary
size.
I choosed 3 for simplicity. And with your solution I cannot match agains
list of arbitrary size.
But I have found the cause of memory consumption. To find it I started to
unfold test function
and found that the recursive call to compose is not strict.

Here is what I did with base implementation:

fna = [(1, 2), (2, 3), (3, 1)]
fni = [(1, 1), (2, 2), (3, 3)]

fldl compose fni (repl 5 fna)

fldl compose fni (fna : repl 4 fna)
fldl compose (compose fni fna) (repl 4 fna)
fldl compose (compose fni fna) (fna : repl 3 fna)
fldl compose (compose (compose fni fna) fna) (repl 3 fna)
fldl compose (compose (compose fni fna) fna) (fna : repl 2 fna)
fldl compose (compose (compose (compose fni fna) fna) fna) (repl 2 fna)
fldl compose (compose (compose (compose fni fna) fna) fna) (fna : repl 1
fna)
fldl compose (compose (compose (compose (compose fni fna) fna) fna) fna)
(repl 1 fna)
fldl compose (compose (compose (compose (compose fni fna) fna) fna) fna)
(fna : repl 0 fna)
fldl compose (compose (compose (compose (compose (compose fni fna) fna) fna)
fna) fna) (repl 0 fna)
fldl compose (compose (compose (compose (compose (compose fni fna) fna) fna)
fna) fna) []

compose (compose (compose (compose (compose ((1, 1) : (2, 2) : (3, 3) : [])
fna) fna) fna) fna) fna
compose (compose (compose (compose ((1, lkup 1 fna) : compose ((2, 2) : (3,
3) : []) fna) fna) fna) fna) fna
compose (compose (compose ((1, lkup (lkup 1 fna) fna) : compose (compose
((2, 2) : (3, 3) : []) fna) fna) fna) fna) fna
compose (compose ((1, lkup (lkup (lkup 1 fna) fna) fna) : compose (compose
(compose ((2, 2) : (3, 3) : []) fna) fna) fna) fna) fna
compose ((1, lkup (lkup (lkup (lkup 1 fna) fna) fna) fna) : compose (compose
(compose (compose ((2, 2) : (3, 3) : []) fna) fna) fna) fna) fna

(1, lkup (lkup (lkup (lkup (lkup 1 fna) fna) fna) fna) fna) : compose
(compose (compose (compose (compose ((2, 2) : (3, 3) : []) fna) fna) fna)
fna) fna
(1, lkup (lkup (lkup (lkup 2 fna) fna) fna) fna) : compose (compose (compose
(compose (compose ((2, 2) : (3, 3) : []) fna) fna) fna) fna) fna
(1, lkup (lkup (lkup 3 fna) fna) fna) : compose (compose (compose (compose
(compose ((2, 2) : (3, 3) : []) fna) fna) fna) fna) fna
(1, lkup (lkup 1 fna) fna) : compose (compose (compose (compose (compose
((2, 2) : (3, 3) : []) fna) fna) fna) fna) fna
(1, lkup 2 fna) : compose (compose (compose (compose (compose ((2, 2) : (3,
3) : []) fna) fna) fna) fna) fna
(1, 3) : compose (compose (compose (compose (compose ((2, 2) : (3, 3) : [])
fna) fna) fna) fna) fna

(1, 3) : (2, lkup (lkup (lkup (lkup (lkup 2 fna) fna) fna) fna) fna) :
compose (compose (compose (compose (compose ((3, 3) : []) fna) fna) fna)
fna) fna
(1, 3) : (2, lkup (lkup (lkup (lkup 3 fna) fna) fna) fna) : compose (compose
(compose (compose (compose ((3, 3) : []) fna) fna) fna) fna) fna
(1, 3) : (2, lkup (lkup (lkup 1 fna) fna) fna) : compose (compose (compose
(compose (compose ((3, 3) : []) fna) fna) fna) fna) fna
(1, 3) : (2, lkup (lkup 2 fna) fna) : compose (compose (compose (compose
(compose ((3, 3) : []) fna) fna) fna) fna) fna
(1, 3) : (2, lkup 3 fna) : compose (compose (compose (compose (compose ((3,
3) : []) fna) fna) fna) fna) fna
(1, 3) : (2, 1) : compose (compose (compose (compose (compose ((3, 3) : [])
fna) fna) fna) fna) fna

(1, 3) : (2, 1) : (3, lkup (lkup (lkup (lkup (lkup 3 fna) fna) fna) fna)
fna) : compose (compose (compose (compose (compose [] fna) fna) fna) fna)
fna
(1, 3) : (2, 1) : (3, lkup (lkup (lkup (lkup 1 fna) fna) fna) fna) : compose
(compose (compose (compose (compose [] fna) fna) fna) fna) fna
(1, 3) : (2, 1) : (3, lkup (lkup (lkup 2 fna) fna) fna) : compose (compose
(compose (compose (compose [] fna) fna) fna) fna) fna
(1, 3) : (2, 1) : (3, lkup (lkup 3 fna) fna) : compose (compose (compose
(compose (compose [] fna) fna) fna) fna) fna
(1, 3) : (2, 1) : (3, lkup 1 fna) : compose (compose (compose (compose
(compose [] fna) fna) fna) fna) fna
(1, 3) : (2, 1) : (3, 2) : compose (compose (compose (compose (compose []
fna) fna) fna) fna) fna

(1, 3) : (2, 1) : (3, 2) : []

The first thing I noticed is that fldl has to be strict to avoid n thunks
for compose evaluation.
The next thing is that compose itself has to be strict with both lkup and
recursive calls strict too.
If I left recursive call non-strict (that is where my problem was) I will
have n thunks for recursive
composition evaluation. If I left call to lkup non-strict I will have n
thunks for mapped value evaluation
for each member of Fn.

n is the amount functions I whant to compose with. I my example this is
1,000,000 functions.

Now I have another question which I'm concerned with. I used foldl' (strict)
in my implementation
instead of just foldl (lazy). Does it mean that libraries are to be in two
implementations one strict
and another one lazy? Because there no way to affect strictness/lazyness of
function without modifying
its implementation. I' going to ask this question as a separate thread.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110722/9a72c3ac/attachment.htm>