Crates (existentials in F#)
The usual blog post introducing crates in F# is G-Research’s. However, I believe that post approaches things from a much more abstract perspective than is useful. Instead, I will approach them by starting from the concrete.
(The crate pattern is also called skolemization, by the way.)
The problem crates solve
Say we want to represent lists in some kind of defunctionalised way.
Because we don’t need to reify each of the individual input lists inside a
ListBuilder, in principle the following could be a much more efficient way to construct the specified list (assuming we define appropriate module methods to deal with currying):
For example, if we did this purely in
List-space, we’d have to reify the concatenated
[ 1 ; 3 ; 10 ; 12 ], whereas in principle we could avoid doing that here: we stand a chance of directly emitting the single output list using the compiler’s built-in magical mutable-tail cons lists which are very fast.
This is all very well, but what about the following extension to the API?
This won’t compile, because we’ve got this type parameter
'b which we’re not generic on.
(The structure I’ve written down is essentially trying to be a generalised algebraic datatype.)
How do we approach this kind of problem?
Let’s drop down a level of abstraction.
To represent sum types in F#, it’s very easy:
But C# doesn’t let you do this! (Well, in ten years C# will have grown to subsume all other programming languages. But as of this writing, it can’t.) How do you approach exactly the same problem in C#?
The canonical trick when your language can’t represent the decomposition of an object is to seal up the object, but teach it how to accept operations from the outside. We can’t take the object to the operation, so we have to take the operation to the object. (This is the “visitor pattern”.)
I’ll present the solution in F# restricted to concepts that are present in C#.
Notice what we’ve done: we have in some sense “taught the discriminated union how to perform operations on itself”, to compensate for the fact that the language can’t express the notion “open up the object to see what’s inside”.
If you wanted to be really object-oriented, you could make an object that represents the operation, and rejig so that
Match now takes an Operation instead:
A little more general
OK, how about the following, where we’re now generic?
Well, the only way this code can make sense is if
toInt also takes an
'a -> int function:
How might we do this in C#? Here’s exactly the same transformation as before:
Again, for the really object-oriented inclined:
How this applies to the Map case
Recall the problematic code:
Well, the language doesn’t give us the tools to “open up” the contents of the Map case. So let’s pull the same visiting trick, starting from the top:
Well, this looks ghastly and also it doesn’t compile (because again there’s that
'b we can’t place anywhere), but happily if we try and make it look nicer by moving to the “really object-oriented” world, both those problems go away!
Now, it’s a little upsetting that the user can’t operate on a nice
OfList case without making one of our nonsense interfaces.
It would be handy if we could retain the terse F# pattern match in all the cases where the language can represent it.
In the following, I just deleted three cases from
Operation, and three implementors of
IListBuilder, and created a discriminated union
ListBuilder which is just “an ordinary ListBuilder, but with an extra case where we have to go through the indirection nonsense”.
I’ll just rename this a bit:
And that is a crate being used as part of the implementation of a GADT.