USE OCAML LANGUAGE Suppose we represent sets by lists The me

USE OCAML LANGUAGE

Suppose we represent sets by lists. The members of the set may appear in any order on the list, but we assume that there is never more than one occurrence of the same element on this list. Write functions to perform the following operations on sets.

a) member (x, S) returns true if element x is a member of the set S; that is, x appears somewhere on the list representing S.

ANSWER:

let rec member x s =
match s with
| [] -> false
| y :: s1 -> if x = y then true else member x s1

b) insert (x,S) puts x on the list for S if it is not already there. Remember that in order to preserve the condition that there no repeating elements on a list that represents a set, we must check that x does not already appear in S; it is not adequate simply to make x the head of the list.?

Solution

type \'a tree = E | T of \'a tree * \'a * \'a tree ;; module type SET = sig type e type s val empty : s val insert : e * s -> s val member : e * s -> bool end ;; module MySet : SET = struct type e = int type s = int tree let empty = E let rec member s = match s with (x , E) -> false | (x , T (a , y , b)) -> if x < y then member (x , a) else if x > y then member (x , b) else true let rec insert s = match s with (x , E) -> T (E , x , E) | (x , T (a , y , b)) -> if x < y then T (insert (x , a) , y , b) else if x > y then T (a , y , insert (x , b)) else T (a , y , b) end ;;