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.