Re: [Caml-list] "List.index" or "List.unique" functions?

[Martin Jambon <martin_jambon@emailuser.net>]

On Fri, 30 Apr 2004, Rahul Siddharthan wrote:

> I just discovered OCaml a week or so ago, and it really seems to be
> the "holy grail" -- more concise and elegant that python, almost as
> fast as C.  I wish I'd known of it a year ago.  Now I just need to get
> used to the functional way of thinking...
>
> I have a question: suppose I have a list l1, and I want to create a new
> list l2 with only one copy of any repeated members of the first list
> (eg, l1=[1;2;3;4;3;4;5;6;5] -> l2=[1;2;3;4;5;6])

1) Naive O(n^2) solution:
let rec unique = function
    [] -> []
  | hd :: tl ->
      if List.mem hd tl then unique tl
      else hd :: unique tl

The result is not sorted.


2) With a hash table you can get something quite efficient (O(n)) and not
too difficult to write:

let unique l =
  let tbl = Hashtbl.create 10 in
  List.iter (fun i -> Hashtbl.replace tbl i ()) l;
  Hashtbl.fold (fun key data accu -> key :: accu) tbl []

The result is not sorted.
You can replace "10" with "List.length l" if really you don't have any
idea of the initial size of the table and want to avoid multiple resizings
of the table.

"fold" functions (List.fold_left, List.fold_right, Hashtbl.fold,
Array.fold_left...) are very useful, and are most of the time more
appropriate than imperative loops ("for" and "while").


3) With sort/simplify (O(n log n)) (I expect it to be much less
efficient than 2)):

let unique l =
  let rec simplify last l =
    match l with
	[] -> [last]
      | hd :: tl ->
	  if hd = last then
	    simplify last tl
	  else
	    last :: simplify hd tl in
  match List.sort compare l with
      [] -> []
    | hd :: tl ->
	simplify hd tl


Martin

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners