Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
Is this an optimal list merging function?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2002-05-08 (10:04)
From: Matt Armstrong <matt@l...>
Subject: Is this an optimal list merging function?
I'm working through some of the exercises available in the O'Reily
book that is available online at <>.

Here is what I came up with for a function that merges two lists. But
I wonder if it is the best solution. It seems like the (accum @
[element]) operations would be O(n) and so the whole function O(n^2).
Or is the @ operator O(1)?

Also, I'm doing a match on (a, b) -- is creating a tuple just for
pattern matching inefficient? Or is ocaml smart enough to not
actually allocate memory for the tuple?

Are there any alternative ways this function could be written short of
replacing the pattern matches with a bunch of if/then expressions?

(* write a function merge_i which takes as input two integer lists sorted
in increasing order and returns a new sorted list containing the
elements of the first two. *)
let merge_i a b =
let rec merge a b accum = match (a, b) with
([], []) -> accum
| ([], head::tail) -> merge [] tail (accum @ [head])
| (head::tail, []) -> merge [] tail (accum @ [head])
| (ahead::atail, bhead::btail) ->
if ahead < bhead then
merge atail b (accum @ [ahead])
merge a btail (accum @ [bhead])
merge a b []

Don't send mail to Duke.Senff@h...
The address is there for spammers to harvest.