A list of types from modules sharing the same signature?

I'm trying to create a bunch of types to generate a MIDI file to be played in a separate audio player (yes, I know there are libraries available... I'm using this as a way to learn). I created a single module signature (while attempting a functor solution) that the various modules containing these types are implementing. The signature looks like this (for now... string will be changed to bytes once I get a working template):

module type MIDIInterface =
    sig
        type t
        val encode : t -> string
    end

The various types I'm creating in different modules/files would be for the various types of MidiEvents: NoteOn, NoteOff, etc. All of them will have an encode function. Because each type is different (differing # of variables, differing event code, etc.), they can't just use the same encode function.

What I want to ultimately do is have a way to fold through all of the events of a song and call each events' encode function to create the full string (eventually bytestring) that can then be saved to a file.

I know I can just create a GADT to put make all of the various types the same type so that I can turn them into a giant list:

type Event =
   | NoteOn  of NoteOnEvent
   | NoteOff of NoteOffEvent
    ...

...but this seems kind of a bulky solution, primarily because I'd have to update that type every time I create a new type. I also know that I can just implement them all under one type and just have one giant encode function:

let encode = function
    | (NoteOn time note velocity) -> ...
    | (NoteOff time note) -> ...

This is the solution I first tried in Haskell, and it was a nightmare to try to read through it when I was looking to reference something (one of the big reasons I'd like to break them into different types in different modules).

Is there a better solution in OCaml to be able to unify these various types based off the same signature without maintaining a big combinatory type into some sort of list/array/collection so that I can "fold encode empty collection_of_events"? If so, can you please let me know what this is called and where I can read up on how it works?

It sounds like you may be looking for the object-oriented side of OCaml. The virtual class midi_interface cannot itself be instantiated and thus is analogous to your module type. As your module type MIDIInterface will create abstract types, the implementation details of the a and b subclasses are opaque.

# class virtual midi_interface =
    object
      method virtual encode : string
    end

  class a =
    object
      inherit midi_interface
      method encode = "a"
    end

  class b =
    object
      inherit midi_interface
      method encode = "b"
    end

  let lst : midi_interface list = [new a; new b]
  let result = List.fold_left (fun i x -> i ^ x#encode) "" lst
;;
class virtual midi_interface :
  object method virtual encode : string end
class a : object method encode : string end
class b : object method encode : string end
val lst : midi_interface list = [<obj>; <obj>]
val result : string = "ab"

And demonstrating the ability to have different variables:

# class c n =
    object
      inherit midi_interface
      method encode =
        let rec replicate s n =
          if n = 0 then ""
          else s ^ replicate s (n - 1)
        in
        replicate "c" n
    end;;
class c : int -> object method encode : string end
# let lst : midi_interface list = [new a; new b; new c 5] in
  List.fold_left (fun i x -> i ^ x#encode) "" lst;;
- : string = "abccccc"

As an added note, it is not strictly speaking necessary for these classes to inherit from midi_interface.

# class d = object
    method encode = "d"
  end;;
class d : object method encode : string end
# let lst : midi_interface list = [new a; new b; new c 5; new d] in
  List.fold_left (fun i x -> i ^ x#encode) "" lst;;
- : string = "abcccccd"

Now, what happens if I fail to define encode for d?

# class d = object
  end;;
class d : object  end
# let lst : midi_interface list = [new a; new b; new c 5; new d] in
  List.fold_left (fun i x -> i ^ x#encode) "" lst;;
Error: This expression has type d
       but an expression was expected of type midi_interface
       The first object type has no method encode

Note that OCaml had no problem with the definition of d without the encode method until I tried to use it. Then it right protested. It would protest the lack of encode even if I removed the type annotation.

# let lst = [new a; new b; new c 5; new d] in
  List.fold_left (fun i x -> i ^ x#encode) "" lst;;
Error: This expression has type d
       but an expression was expected of type a
       The first object type has no method encode

But, if I explicitly say that d inherits from midi_interface the compiler will complain if I fail to implement encode as soon as I try to define d rather than when I try to use it.

# class d = object
    inherit midi_interface
  end;;
Error: This non-virtual class has virtual methods.
       The following methods are virtual : encode

@Chris has provided a very good, working answer, but I feel something can be added. Quick detour about software design before I give more details.

Roughly, there are two "directions" in which you could expand your software, which is either adding different kinds of data, or adding different ways of operating of data. These are called, respectively, vertical and horizontal extensions (I won't get into the details about these names).

OCaml usually favors horizontal extensions: once a sum type has been defined, which covers all the possible data that your program has to process, it's easy to add new functions that operate on that data (it's a match). Most importantly, it's a local change, that doesn't require modifying the rest of the code. In fact, the rest of the code could very well be precompiled, that doesn't prevent you from adding a function. On the other hand, if you wanted to add new kind of datatypes, you'd have to modify the original type (to add a new case) and every function that operates on them, because their pattern matching will no longer be exhaustive. This is a non-local change, and you need the source code of the rest of the project to make a small addendum.

OO programing languages, on the contrary, usually support vertical extensions better. It's easy to extend an existing type hierarchy by inheriting an existing class. Again, it's a local change (just the code you add), and it could even work with precompiled stuff. However, adding a method is now costly, because you'd have to modify every class already defined (which is non-local) and, for most compiled languages, that can't be done on precompiled blobs.

As an example, think of a game with some entities (a player, sheeps, ...). In OCaml, you could represent all the entities in a big enum (type entity = Player of ... | Sheep of ... | ...) whereas in an OO language, you'd rather use a class hierarchy. A horizontal extension would be, for instance, the possibility for each entity to make some sounds. In OCaml, you'd define a function Player _ -> "claps" | Sheep _ -> "bleat" | ..., whereas in an OO language, you'd have to add a method to each existing class. A vertical extension could be adding a new entity, say, a zombie. In OCaml, that would require changing the type entity and every function that pattern matches on it, whereas in an OO language, that would just mean creating a new class.

In fact, OCaml supports (as we will see) several ways to design software that is easily extensible vertically, instead of horizontally. The main point of this preliminary explanation was: when you choose which technique you use to solve your problem, the first thing that you should consider is what kind of extensions you want to make easy. There are other tradeoffs in the approaches I will enumerate, but IMO they are minor with respect what kind of modifications you make easy to perform.

An other thing to note is that, whatever the approach you will chose, you will eventually write more or less the same amount of code, it will just be grouped differently.

You, evidently, already know about algebraic datatypes, which are the most straightforward way to encode data. As you have noted, however, using this way favors horizontal extensions, which means grouping data types on the one side, and functions on the other side. This is very efficient (with respect to what we will see later on).

I'll just drop a line here about polymorphic variants, which allow a little more freedom, but come at a (usually negligible) additional cost. They can serve as a middle man between ADT and what comes next, but since it's likely not the best solution specifically for the question you asked, I won't add more details.

As I mentioned earlier, there is more than one solution to make vertical extensions easier (the obvious one being OOP). I will talk about two of them; both of them rely on dynamic dispatch, that is, type erasure (we forget about the exact type during the compilation) coupled with some runtime information to compensate for the information loss at compile time.

The first way of doing this is with OOP. For your information, OOP in OCaml is very different from what it looks like in other languages (classes are not types, objects are not bound to a specific class but, instead, are simply typed according to what they can do, ...). For this reason, it integrates pretty well with the style of the rest of the language. OCaml, in this aspect as in many others, is pragmatic instead of trying to be "pure" or elegant.

In OOP, the type erasure works with subtyping. If A is a subtype of B, then any value a: A can be though of as a value of type B (typically, any specific cat can be though as a cat, or as an animal, which is less specific). Since the true, underlying type of a given object is never truly known (because anyone could have created a subclass of the class you where expecting), it's impossible to resolve at compile time which methods should be called. Instead, each object carries some metadata which allows computing at runtime the actual function to be called on a method dispatch.

However, in OCaml, there is an other way to have dynamic dispatch: it's reified modules (or first-class modules, like in first-class functions). It's a terrific feature, that allows you to turn any module into a regular value. Before going into details, I'd like to show you the same example as @Chris, but done with modules:

#
module type MidiInterface = sig
  val encode : unit -> string
end

module A: MidiInterface = struct
  let encode () = "a"
end

module B: MidiInterface = struct
  let encode () = "b"
end

let lst : (module MidiInterface) list = [(module A); (module B)]
let result = List.fold_left (fun i (module X: MidiInterface) -> i ^ X.encode ()) "" lst;;
module type MidiInterface = sig val encode : unit -> string end
module A : MidiInterface
module B : MidiInterface
val lst : (module MidiInterface) list = [<module>; <module>]
val result : string = "ab"
#

and

#
let c : int -> (module MidiInterface) = fun n -> (module struct
  let encode () =
    let rec replicate s n =
      if n = 0 then ""
      else s ^ replicate s (n-1) in
    replicate "c" n
end);;
val c : int -> (module MidiInterface) = <fun>
# let lst : (module MidiInterface) list = [(module A); (module B); c 5] in
List.fold_left (fun i (module X: MidiInterface) -> i ^ X.encode ()) "" lst;;
- : string = "abccccc"
#

As you can see, it's quite natural (if you are acquainted with modules in OCaml) to "turn dynamic dispatch on" in otherwise "regular" OCaml code. Also note that, beside the few syntactic differences, my code and the one @Chris wrote are very similar. We both start with an abstract declaration of the information we want to erase at compiled time (here, the actual encode function / method). Then, we instantiate some values that satisfy the declaration, and erase they actual type. Finally, we dispatch the method / function call.

In general, modules are much, much more powerful than objects in OCaml, but that comes at a cost: note that most of the typing information I had to provide, contrary to what you are used to in OCaml, was not optional. Type inference of modules is much harder than usual type inference, and so we have to help the compiler a little more (which is, all in all, not that bad, since it's helpful for the reader). Furthermore, whereas with objects the syntax is very lightweight, with modules you have to explicitly tell OCaml when you want to "box" them as regular, opaque values, and when you want to retrieve the boxed module.

As a personal note, I have never seen objects being used in "real" OCaml code. I know that somewhere, someone uses that feature but, whenever I read (or wrote) code that was appropriate for OOP, modules where used instead, despite being more syntactically heavy. I'm not sure why. Maybe it's because modules work better with functors defined in other libraries.