12 Implementing Representation Invariants

Implementing the representation invariant is good!

Idiom:

• Write a rep_ok function
• Call function on every input and output

let rep_ok (x : t) : t =
    if (* check_ri *) then x
    else failwith "RI"

This is another example of defensive programming.

Let's implement it for ListSet.

module ListSetDups = struct
	(** The list [[a1; ...; an]] represents the set {a1, ..., an}
		[[]] represents the empty set.
		The list may not contain duplicates *)
	type 'a t = 'a list
	
	let dedup lst = lst |> List.sort_uniq Stdlib.compare
	
	let rep_ok lst =
		if List.length lst = List.length (dedup lst) then lst
		else failwith "RI"
	
	let empty = rep_ok []
	
	let size lst = List.length (rep_ok lst)
	
	let add x s = if List.mem x (rep_ok s) then s else x :: s
	
	let mem s = List.mem (rep_ok s)
	
	let union s1 s2 =  (rep_ok s1) @ (rep_ok s2) |> dedup
end

module ListSetDups :
  sig
    type 'a t = 'a list
    val dedup : 'a list -> 'a list
    val rep_ok : 'a list -> 'a list
    val empty : 'a list
    val size : 'a list -> int
    val add : 'a -> 'a list -> 'a list
    val mem : 'a list -> 'a list list -> bool
    val union : 'a list -> 'a list -> 'a list
  end

This is an expensive way to code. You probably don't want to do this in a production enviorment. Possibly, you want to be able to turn on rep_ok, or replace it with something similar. For example, you could replace rep_ok with let rep_ok lst = lst, then if you ever need to do a hotfix, you can find the bug right away. This is another really good example of defensive programming.