OCaml - Expression was expected of type 'b list

0
votes

I'm trying to write a function that checks whether a set (denoted by a list) is a subset of another.

I already wrote a helper function that gives me the intersection:

let rec intersect_helper a b =
    match a, b with
    | [], _ -> []
    | _, [] -> []
    | ah :: at, bh :: bt ->
        if ah > bh then
            intersect_helper a bt
        else if ah < bh then
            intersect_helper at b
        else
            ah :: intersect_helper at bt

I'm trying to use this inside of the subset function (if A is a subset of B, then A = A intersect B):

let subset a_ b_ =
    let a = List.sort_uniq a_
    and b = List.sort_uniq b_
    in intersect_helper a b;;

Error: This expression has type 'a list -> 'a list but an expression was expected of type 'b list

What exactly is wrong here? I can use intersect_helper perfectly fine by itself, but calling it with lists here does not work. From what I know about 'a, it's just a placeholder for the first argument type. Shouldn't the lists also be of type 'a list?

2
ocamltypeerror

2 Answers

2
votes

I'm glad you could solve your own problem, but your code seems exceedingly intricate to me.

If I understood correctly, you want a function that tells whether a list is a subset of another list. Put another way, you want to know whether all elements of list a are present in list b.

Thus, the signature of your function should be

val subset : 'a list -> 'a list -> bool

The standard library comes with a variety of functions to manipulate lists.

let subset l1 l2 =
  List.for_all (fun x -> List.mem x l2) l1

List.for_all checks that all elements in a list satisfy a given condition. List.mem checks whether a value is present in a list.

And there you have it. Let's check the results:

# subset [1;2;3] [4;2;3;5;1];;
- : bool = true

# subset [1;2;6] [4;2;3;5;1];;
- : bool = false

# subset [1;1;1] [1;1];; (* Doesn't work with duplicates, though. *)
- : bool = true

Remark: A tiny perk of using List.for_all is that it is a short-circuit operator. That means that it will stop whenever an item doesn't match, which results in better performance overall.

Also, since you specifically asked about sets, the standard library has a module for them. However, sets are a bit more complicated to use because they need you to create new modules using a functor.

module Int = struct
  type t = int
  let compare = Pervasives.compare
end

module IntSet = Set.Make(Int)

The extra overhead is worth it though, because now IntSet can use the whole Set interface, which includes the IntSet.subset function.

# IntSet.subset (IntSet.of_list [1;2;3]) (IntSet.subset [4;2;3;5;1]);;
- : bool = true
0
votes

Instead of:

let a = List.sort_uniq a_

Should instead call:

let a = List.sort_uniq compare a_