Hello!

Quote:

>Can anyone explains to me how to merger two lists of integers in

>Hugs/Gofer in an efficent manner rather than doing 2^n recursive calls.

>I mean, is it possible to do a merge of 2 sorted list with lg n, or even

>1, recursive call?

Hmmm.

merge :: Ord a => [a] -> [a] -> [a]

merge [] xs = xs

merge xs [] = xs

merge (x:xs) (y:ys) | x < y = x:merge xs (y:ys)

| True = y:merge (x:xs) ys

The number of recursive calls is linear in the length of the results.

And, in fact, usually the stack will need constant size because of

lazy evaluation.

So, the time is linear (you can't get better if the input is present

as linear lists), and the space is constant (plus the space for the

elements, of course). What do you want more?! 8:-)

Regards, Felix.