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  
 
 [ 3 post ] 

 Relevant Pages 

1. help! f90.help help help help

2. ***HELP***HELP***NEED INFORMATION***HELP***HELP

3. HELP HELP HELP HELP

4. HELP HELP HELP HELP

5. Ord Function HELP Please HELP HELP HELP

6. help help help help!!!!!!!!!!!

7. (HELP (HELP (HELP (HELP))))

8. HELP: HELP: HELP: HELP: Online-manual on Expect

9. Help Help Help

10. TopSpeed - ODBC 3.1???? HELP HELP HELP

11. HELP - HELP - HELP

12. HELP HELP HELP - round function error

 

 
Powered by phpBB® Forum Software