Help
Author Message
Help

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?

thanks in advance for any response.

Wed, 24 Jan 2001 03:00:00 GMT
Help

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

You can build a tree and then build a list from the tree.

--

http://www.gemstone.com

Wed, 24 Jan 2001 03:00:00 GMT
Help
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.

Wed, 24 Jan 2001 03:00:00 GMT

 Page 1 of 1 [ 3 post ]

Relevant Pages