No type constructor for record types?

Question

I translated the following Haskell code into OCaml:

data NFA qs = NFA { intialState :: q , isAccepting :: q -> Bool , transition :: q -> s -> [q] } 

I originally tried a very literal translation:

 type ('q,'s) nfa = NFA of { initialState: 'q; isAccepting: 'q -> bool; transition: 'q -> -> 'q list } 

... and, of course, this gives a syntax error, because part of the constructor of the "NFA of" type is not allowed. It should be:

  type ('q,'s) nfa = { initialState: 'q; isAccepting: 'q -> bool; transition: 'q -> -> 'q list } 

This made me wonder why this is so. Why don't you have a constructor type for a record type, as you could for a tuple type (as shown below)?

 type ('q, 's) dfa = NFA of ('q * ('q->bool) * ( 'q -> -> 'q list) ) 

Answer 1

Why do you need a type constructor for record types, except what is your habit in Haskell?

In Haskell, records are not exactly first-class constructs: they are more like syntactic sugar on top of tuples. You can define the name of the record field, use them as accessories and perform a partial update of the record, but this frees you from accessing the positions in simple tuples. Therefore, the name of the constructor must be reported to one record from another after desugaring: if you did not have the name of the constructor, two records with different field names, but the same field types will desugar into equivalent types, which would be bad.

In OCaml, entries are a primitive concept, and they have their own identity. Therefore, they do not need a head constructor to distinguish them from tuples or records of the same field types. I don’t understand why you would like to add a head constructor, as it is in more detail, without giving more information or helping expressiveness.

Why don't you have a constructor type for a record type in the same way you could for a tuple type (as shown below)?

Be careful! In the example that you are showing, there is no tuple, only the type of the sum with several parameters. Foo of bar * baz is not the same as Foo of (bar * baz) : the first constructor has two parameters, and the last constructor has only one parameter, which is a tuple. This differentiation is performed for performance reasons (in memory, both parameters are packed together with the constructor tag, while the tuple creates an indirection pointer). Using tuples instead of multiparameters is somewhat more flexible: you can match both Foo (x, y) -> ... and Foo p -> ... , and the latter are not available for multiparameter constructors.

There is no asymmetry between tuples and records, since none of them has a special status in a construction such as a sum, which is just the sum of the constructors of an arbitrary arity. However, it is easier to use tuples as parameter types for constructors, since tuple types do not have to be declared for use. For instance. some people asked to write

 type foo = | Foo of { x : int; y : int } | Bar of { z : foo list } 

instead of the current

 type foo = Foo of foo_t | Bar of bar_t and foo_t = { x : int; y : int } and bar_t = { z : foo list } 

Your request is a specific (and not very interesting) case of this question. However, even with this shorthand syntax, there is still one pointer to a pointer between the constructor and the data, which makes this style unattractive for performance-oriented programs. What might be useful is the ability to have named constructor parameters.

PS: I'm not saying that choosing Haskell from desugaring records in tuples is bad. By translating one function into another, you reduce the redundancy / overlap of concepts. Nevertheless, I personally think that it would be more natural to select tuples in a record (with numerical field names, as was done, for example, in Oz). In programming a programming language, there are often no "good" and "bad" options, only different compromises.

Answer 2

You cannot get it because the language does not support it. Actually, it would be easy to fit into a type system or data representation, but it would be a little additional complication in the compiler, and this was not done. So yes, you need to choose between the constructor name and the argument naming.

Note that the names of the record labels are {initialState=q} with a specific type, for example, {initialState=q} is a template of the type ('q, 's) nfa ; You cannot reuse the label name in another type. Therefore, naming a constructor is really useful when a type has several constructors; then if you have many arguments for the constructor, you can define a separate type for the arguments.

I believe that there is a patch for this function, but I don’t know if it is updated for the latest version of OCaml or something else, and this will require that someone using your code have this patch.