Additionally, tthe functions he uses to split the list are not tail recursive, and will blow up on longer lists. The same is true of his merge function. To avoid the second problem, one can do reverse sorts followed by reverse merges that build up the result in an accumulator as in this version of dispatch. See the sort implementation in list.ml for an example of this.
On 8/28/08, Christopher L Conway <[EMAIL PROTECTED]> wrote: > > > Pereira, > > The only comment I have is that your dispatch function scans the list > twice (once for odds, once for evens) when it doesn't have to. For > example: > > let dispatch xs = > let rec aux (odds,evens) xs = > match xs with > | [] -> odds, evens > | x :: [] -> x :: odds, evens > | x :: y :: zs -> aux (x :: odds, y :: evens) zs > in aux ([],[]) xs > > Regards, > Chris > > On Thu, Aug 28, 2008 at 8:21 AM, Pereira Lucien > <[EMAIL PROTECTED]> wrote: > > > > Hi, > > > > I'm interested in improve my skills concerning OCaml language. It > > should be nice to give me > > you opinion about this code. Is it optimal ? Do I respect functionnal > > programation style ? > > Do you have another implementation to propose ? > > > > Thanks > > > > (* > > * return an half list (odd positions) > > *) > > let rec oddElements list = match list with > > [] -> [] > > | head::_::tail -> head::(oddElements tail) > > | head::[] -> head::[] > > > > (* > > * return an half list (even positions) > > *) > > let rec evenElements list = match list with > > [] -> [] > > | _::a::tail -> a::(evenElements tail) > > | _::[] -> [] > > > > (* > > * Split a list, returns a couple of half list > > *) > > let dispatch list = (oddElements list, evenElements list) > > > > (* > > * Merge two sorted list in order to return a sorted list too > > *) > > let rec merge (list1, list2) rel = match (list1, list2) with > > (hd1::tl1, hd2::tl2) -> > > begin if rel hd1 hd2 <= 0 then hd1::(merge (tl1, list2) rel) > > else hd2::(merge (list1, tl2) rel) > > end > > | ([], _) -> list2 > > | _ -> list1 > > > > (* > > * Ordinary relation function for integers > > *) > > let relInt a b = if (a < b) then -1 else > > begin if (a > b) then 1 > > else 0 > > end > > > > (* > > * The mergeSort itself, It works ! ;) > > *) > > let rec mergeSort list rel = match list with > > [] -> [] > > | a::[] -> a::[] > > | _ -> let (a,b)=dispatch list in > > let c=mergeSort a rel in > > let d=mergeSort b rel in merge (c,d) rel > > > > > > > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "ocaml-developer" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/ocaml-developer?hl=en For other OCaml forums, see http://caml.inria.fr/resources/forums.en.html -~----------~----~----~----~------~----~------~--~---
