Operations over sets

sets.ml

let rec member x = function
    | [] -> false
    | h :: t when x = h -> true
    | h :: t -> member x t

let rec subset a = function (* quite dumb, in O(n²) *)
    | [] -> true
    | h :: t when (member h a) -> subset a t
    | h :: t -> false

let equal a b = (subset a b) && (subset b a) (* O(n²) *)

let inter a b =
    let rec inter_aux a acc = match a with
        | [] -> acc
        | h :: t when (member h b) -> inter_aux t (h :: acc)
        | h :: t -> inter_aux t acc
    in
    inter_aux a []

let union a b =
    let rec union_aux a b = match a with
        | [] -> b
        | h :: t when (member h b) -> union_aux t b
        | h :: t -> union_aux t (h :: b)
    in
    union_aux a b

let diff a b =
    let rec diff_aux a acc = match a with
        | [] -> acc
        | h :: t when (member h b) -> diff_aux t acc
        | h :: t -> diff_aux t (h :: acc)
    in
    diff_aux a []