Return elements common in both lists in Ocaml

Question

I need to implement a method to return common elements in two lists as part of an assignment problem: My idea was to remove duplicates in both lists, concatenate them and return elements that are repeated in the resulting list. I want to define a Boolean function that check for each elements in the list if they appear more than once. My idea was to use List.fold_left with a specific element b in the list and use acc to keep track of the number of times it appears in the list. However, I have an error here:

I have another idea that involves sorting the lists first, But the list could be of any type, hence comparison has to be implemented for new types as well. Or can I just use < to compare any type of values?

Here are the codes that I have so far.

let rec remove (b : 'a) (l : 'a list)=
  match l with
  | [] -> []
  | w::e -> if w=b then remove b e
      else w::(remove b e)

let rec removeduplicates (l:'a list)=
  match l with 
  | [] -> []
  | w::e -> w::(removeduplicates(remove w e))

let removeduppair (l : 'a list * 'a list)=
  let (l1,l2) = l in
  (removeduplicates l1, removeduplicates l2)

That will be awfully slow O(n^2) and limited by the stack size. To make this efficient you have two options: 1) As you mentioned: sorting. This would be O(n log n). or 2) hashing. O(n). Create Hashtbl's using the items in the lists as keys (and () as value) and then check if keys from the first are in the second too. — Goswin von Brederlow

Jeffrey Scofield Jeffrey Scofield · Accepted Answer · 2019-01-26T17:42:36

This expression has a type error:

if x = b then acc + 1

The problem is that doesn't have an else part. In other words, it doesn't say what you want the value to be when x is not equal to b.

You can fix this just by adding an else part.

A little more detail: OCaml allows you to leave off the else part, but only if the then part has unit type. In such a case, the value when the test is false will be the same as when it is true, namely () (the only value of unit type).

Return elements common in both lists in Ocaml

1 Answers