CODEWITHSUNDEEP
ocaml
daniele3004
daniele3004

Reputation: 13920

How to search duplicated in OCaml List?

I have a list like this:

let myList = [(1,2,1);(5,1,4);(10,2,8);(6,0,4)];;

I want a function that return true when in third position there are value already present in others third position. In this example (5,1,4);(6,0,4). --search duplicates--

Thank you

Upvotes: 1

Views: 1887

Answers (2)

coredump
coredump

Reputation: 38809

Another approach consists in using a hash table to mark elements that are visited. As soon as you find a duplicate, return true. Otherwise, return false.

exception Found;

let has_dup list =
  let hash = Hashtbl.create (List.length list) in
  try
    begin
      List.iter (function (_,_,x) ->
                  if (Hashtbl.mem hash x)
                  then (raise Found)
                  else (Hashtbl.add hash x true))
                list;
      false
    end
  with Found -> true ;;

You don't really need to compute the length of list when building the hash table. That part might be replaced by a constant (the hash table will grow).

Upvotes: 2

Marth
Marth

Reputation: 24812

You have two approaches when searching for duplicates:

  • sort the list and compare successive elements (O(nlg(n))
  • use an auxiliary structure (takes more memory)

An way of doing it sorting the list:

# let dup_exists l =
  let rec dup_consecutive = function
    | [] | [_] -> false
    | (_ ,_ ,e1)::((_ ,_ ,e2) as h2)::tl -> e1 = e2 || dup_consecutive (h2::tl)
  in
  let sort_on_third (_, _, e1) (_, _, e2) = compare e1 e2 in
    dup_consecutive (List.sort sort_on_third l);;
val dup_exists : ('a * 'b * 'c) list -> bool = <fun>

# let myList = [(1,2,1);(5,1,4);(10,2,8);(6,0,4)];;
val myList : (int * int * int) list =
  [(1, 2, 1); (5, 1, 4); (10, 2, 8); (6, 0, 4)]
# dup_exists myList;;
- : bool = true
# let myList = [(1,2,1);(5,1,4);(10,2,8);(6,0,10)];;
val myList : (int * int * int) list =
  [(1, 2, 1); (5, 1, 4); (10, 2, 8); (6, 0, 10)]
# dup_exists myList;;
- : bool = false

Upvotes: 2

Related Questions