OCaml: find value of specific type

Question

I have the list of some values where I need to find out which kind of value is first:

type my_types =
    | MAlpha
    | MBeta of int list
    | MGamma of string * int

let find_first where what =
    List.iter ( fun m ->
        | MAlpha ->
            (* iterate frough "what" to find if it was asked to look and return it if it was *)
        | (* do the same for all other types *)
    ) where;
;;

let main =
    let where_to_find = [MGamma, MAlpha, MBeta] in
    let what_to_find = [MAlpha, MBeta] in
    (match (first_found where_to_find what_to_find) with
    | MAlpha ->
        (* should return this *)
    )
;;

Is there a way to do so without touching all types of MyType within find_first - is it possible to compare types of two values? Thank you.

Answer 1

Another way to look at this is that you have an equivalence relation for your type; i.e., you have some places where you want to treat all the MAlphas the same, all the MBetas the same, and all the MGammas the same. A standard handling for equivalence relations is to pick a representative element that represents the whole set of equivalent values (the equivalence class).

In your case you could use MAlpha to represent all the MAlphas (but there's only one of them), MBeta [] to represent all the MBetas and MGamma ("", 0) to represent all the MGammas. You would have a function to calculate the representative value from a given one:

let malpha = MAlpha
let mbeta = MBeta []
let mgamma = MGamma ("", 0)

let canonicalize =
    function
    | MAlpha -> malpha
    | MBeta _ -> mbeta
    | MGamma _ -> mgamma

let find_first where what =
    canonicalize (List.find (fun x -> List.mem (canonicalize x) what) where)

let main () =
    let where_to_find = [MGamma ("a", 3); MAlpha; MBeta [3; 4]] in
    let what_to_find = [malpha; mbeta] in
    try
        let found = find_first where_to_find what_to_find
        in
            if found = malpha then (* what to do *)
            else if found = mbeta then (* what to do *)
            else (* what to do *)
    with Not_found -> (* nothing was there *)

I have written code like this and it doesn't come out too bad. In your case it allows you to specify the what parameter a little bit naturally. One downside, though, is that you can't pattern match against malpha, mbeta, and mgamma. You have to do equality comparisons against them.

It may be that you wanted to find the specific value in the list, rather than the canonicalized value. I think the changes for that case should be pretty clear.

This also answers the second part of your question. The List.find function will stop as soon as it finds what it's looking for.

OCaml defines an ordering relation for all types that don't contain functional values in them. If this built-in (polymorphic) ordering doesn't do what you want, you have to define your own. You would certainly need to do this to compare values of two different types; but that is not what you're doing here.

If there's no element in the list that looks like what you said you wanted, this version of find_first will raise the exception Not_found. That's something else to think about.

Answer 2

The code you have posted would not compile, but I think you are looking for the following information:

1. It is possible to write so-called or-patterns, as in, for instance, (function MAlpha | MBeta _ -> ...).

2. But patterns are not first-class citizens. You cannot build a pattern from a list (and by the way, [MGamma, MAlpha, MBeta] is one of the things that does not compile in your question), nor can you pass a pattern as argument to a function.

3. However, you can build and pass around a function that matches for a pattern, so if you are willing to change your function find_first to take a function instead of a list for what, it will be more convenient to use.