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

[Caml-list] "List.index" or "List.unique" functions?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2004-04-30 (18:51) From: Martin Jambon Subject: Re: [Caml-list] "List.index" or "List.unique" functions?
```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

```