module Make(Ord: OrderedType) =
struct
type elt = Ord.t
type t = Empty | Node of {l:t; v:elt; r:t; h:int}
let is_empty = function Empty -> true | _ -> false
let rec add x = function
Empty -> Node{l=Empty; v=x; r=Empty; h=1}
| Node{l; v; r} as t ->
let c = Ord.compare x v in
if c = 0 then t else
if c < 0 then
let ll = add x l in
if l == ll then t else bal ll v r
else
let rr = add x r in
if r == rr then t else bal l v rr
end
Polymorphic record version. The implementation of make_set_functions is dummy for simplicity:
type 'a ordered_type_functions_t = {
compare: 'a -> 'a -> int;
}
type 'a set_t =
| Empty
| Node of {l: 'a set_t; v: 'a; r: 'a set_t; h: int}
let make_set_functions (ord: 'elt ordered_type_functions_t) : ('elt, 'elt set_t) set_functions_t = {
is_empty = (fun (set: 'elt set_t) -> false);
add = (fun (new_elem: 'elt) (old_set: 'elt set_t) -> old_set);
}
It seems that polymorphic records can do what first-class modules do.
With modules, I can define a functor (let’s say) for the type of hash-consed things of type t, viz.
module Intern(T : sig type it val hash t -> int end) : sig type t ..... end = struct
type t = HC of T.it
.... code to implement a hashtable mapping T.it to t
end
and then I can apply that functor to two different types to get two different modules, and two different types t. I can apply that functor twice to the same type and get two different types t that are distinct at compile time, even if identical at runtime. An example being (let’s say) strings in a compiler, where I want to have two different namespace for type-names and variable-names. They’re both strings, but I want them distinct as types in my compiler’s code.
I don’t know how I’d do this with records. Also, the values of type t don’t carry any function-pointers – just the data. Whereas with records, the typical way you use 'em is kind fo like O-O: you have to carry along all the function-pointers, and that makes them fatter in memory.
Here’s one example of why generating new types is important, using the set idea from before.
module StringSet = Set.Make (String)
module CaseInsensitiveStringSet = Set.Make (struct
type t = string
let compare a b = String.compare (String.lowercase_ascii a) (String.lowercase_ascii b)
end)
(There are probably more robust ways to implement a case-insensitive string set, but this is just an example.)
Both of these sets have type elt = string but their t types are not equal. This is good, because we don’t want to create a case-insensitive string set and then try to add an element with the normal string set’s add function. The Set.Make functor takes care of that type inequality for us, since modules are able to declare new types.
But with a record of functions, we lose all guarantees that an arbitrary 'a set record will behave the way we expect. If we try to implement our two string sets that way, then we just end up with two values with equal string set types. We could apply a case-sensitive add to a case-insensitive set, which we don’t want.
@JohnJ@Chet_Murthy
I just realized that I can write the functor Set.Make using polymorphic records. And your examples can be done with polymorphic records.
JohnJ’s example (make_set_functions is the counterpart of the functor Set.Make):
Yes. But since here I take the trouble to write make_set_functions etc, I’ll use string_set_functions (or case_insensitive_string_set_functions). I don’t see a problem here.
The point of generative types, is that when you construct a set using case-insensitive-set operations, you cannot hand that set to string-set operations. The type system prevents it. That’s the point of generative types: types that are structurally identical, are still different and values of those types cannot be intermingled.
I think generative types make modules somewhat akin to classes in Java. A module is not just a collection of functions, but data + methods. Is that good?
Everything I said above about “modules” was really about modules per se: I rarely if ever use the “first class” nature of modules in OCaml. Sure, it all applies there too, but again, I rarely-if-ever use that.
I would not say that, no. A generative type need not have any functions associated with it. (Just making something up) if you declare a type twice – the same identical type – in two different modules, then values of those two types are not interchangeable. And functions that work on the first, will not work on the second. Those functions don’t need to be declarated in the modules where the types were declared.
I hope I’m being clear. It is the types themselves that are distinct. And types can be distinct even if they are identical structurally in every way. This is what I meant by my functor that produces a module of hash-consed strings: if you apply it twice, you want to get two different modules, with two different types, and you want that you cannot intermingle hash-consed values of the first modules, with those of the second module.
I’m seeing two different questions here, whether or not FCMs are more powerful and whether or not FCMs are more practical. They are certainly more powerful, but I agree that their extra power is often not needed for everyday problems. If you just need to pass some functions around internally without too much fuss, then there’s nothing wrong with creating a record of functions.
But things like FCMs and functors are important when you have a library that other users will access. In that situation, you need to be able to guarantee that your users won’t be able to misuse your library. Creating new types inside modules is an easy way to do that.
Just for the record - other people might not be using FCM in everyday code, but I do it a lot mixed with functional reactive programming. I see the mix of FCM + FRP as a kind of declarative and pure alternative to OO.
In can go more in depth if someone is interested - the overall design is to start programming without FCM and having toplevel reactive values within modules. Then when you need a part of the reactive graph to be instantiated dynamically and potentially run concurrently, then you can make your modules into functors, instantiated as FCMs.
No havn’t got anything opensourced currently, but it’s proven a good design pattern of several of my bigger FRP codebases (a visual synthesizer and a modular synthesizer rhythm-module). If you have any specific questions I’ll be glad to answer them - otherwise I’m thinking of making a blogpost on it at some point.
I don’t have any specific questions. I think I understand the basic idea, so I was mostly just curious to see a concrete example of how you’ve applied/used the pattern you describe. Consider this a +1 vote for a blog post.
