How to do pattern matching for abstract data type in OCaml?

Question

I have a set T, which have elements of the form int*< Abstract>*int.

I want to find a element of this set which is of the form, say 4*< Abstract>*5.

When i try to use

match T with 
|(4,_,5) -> Printf.printf "yes"
|(_,_,_) -> Printf.printf "no"

I am getting an error which says "Error: This expression has type transitionSet but an expression was expected of type loc * 'a * loc "

How to find an element in the set?

Answer 1

Set is abstract therefore no way to pattern match itself. Within OCaml's standard library Set module, what you can do is to filter the set then check it is_empty or not:

Set.(is_empty @@ filter p t)

where p is your predicate.

Answer 2

I'm assuming your set module is called TSet and you are using OCaml standard library sets. I'm also assuming your set isn't really called T, since that is not a valid name for OCaml variables.

If you only care about a yes/no answer for whether a single matching value exists, you can do:

let result =
  TSet.exists
    (function
    | 4, _, 5 -> true
    | _       -> false)
    t in
if result then print_endline "yes" else print_endline "no"

In general, whatever your predicate is, you can do

TSet.exists p t

---

If you want more than a yes/no answer, and want to be able to perform arbitrary computations in the case branches on all the matching values in the set, you will have to use fold or iter with pattern matching. For example, if you want to add all the first integers together, but only when the last integer is 5:

TSet.fold
  (fun element accumulator ->
    match element with
    | x, _, 5 -> x + accumulator
    | _       -> accumulator)
  t 0

---

If you want to perform the computation only on the first matching element, you can short-circuit evaluation with an exception. For example:

exception Found of int

try
  TSet.iter
    (function
    | x, _, 5 -> raise_notrace (Found x)
    | _       -> ())
    t;
  None
with Found x -> Some x

This last one is awkward to type over and over. You can write a polymorphic function to solve the problem of short-circuiting pattern-matching search for yourself by using a reference and the built-in Exit exception. I'll leave that as an exercise.

It's a good idea to use raise_notrace since this exception is being used for normal flow control. If your program is one day compiled with stack traces enabled, raise_notrace will omit the stack trace when throwing the exception, which could make your program faster if your function is called often.

For your reference, http://caml.inria.fr/pub/docs/manual-ocaml/libref/Set.S.html