Folding over fields

One of the best features of ML is pattern matching. Pattern matching is essentially a way of writing a case analysis driven by the structure of the data. The thing that makes pattern matching such a phenomenal tool is the type-checking discipline that is associated with it. In particular, the compiler checks that pattern matches are exhaustive and non-redundant. This is helpful when writing a case analysis for the first time, but the value of the technique really shows itself as the code evolves. In the absence of such checks, it's easy for a case analysis to silently become incomplete as the underlying data structures change, thus letting bugs creep in.

Pattern matching makes it easy to make sure that a case analysis is exhaustive, but there are other kinds of exhaustiveness that we might want static checks for where the compiler provides no help. One example we see a lot comes up in the context of validation. In a lot of the code we write, it is necessary to validate a configuration value represented as a record, and we want to make sure that every record field is explicitly checked.

After hearing me complain about how little help the language provided in this case, Steven proposed an elegant solution: use a macro to generate for any record definition a function that folds over the fields in that record. Thus, if you declare a record as follows:

module M = struct
  type t = { foo: int;
             bar: float;
             snoo: (int * string) list; }
  with field_fold
end

you would end up with the following signature

module M : sig
  type t = { foo: int;
             bar: float;
             snoo: (int * string) list; }
 
  val field_fold :
     t -> 'a
     -> foo : (int -> 'a -> 'a)
     -> bar : (float -> 'a -> 'a)
     -> snoo : ((int * string) list -> 'a -> 'a)
     -> 'a
end

By writing your validation function around field_fold, you can make sure that the validation catches every field in the record, even as the definition of the record changes over time. But this idiom is not really specific to the validation case. You can use it just as well in other situations where exhaustiveness is important, such as writing an equality function or writing code to serialize a record.

We haven't implemented this yet, but it's coming. The version we're going to do is a little bit more sophisticated that what I've described here. We already have a set of macros for generating values representing each field in a record that can be used for getting and setting values and which contain a string representation of the name of the field. I expect our field_fold will be based on these field representatives rather just on the raw values. I expect this all will eventually find its way into a public release of core.