How to "merge" unknown tuples?

For relational programming I need an ability to join collections (relations) of tuples. Very simplified version of what I need looks like:

Rel.join [(1; "James")] [(1; 34)]  (* returns:  [(1; "James"; 34)] *)

How can I do this without knowing actual types of tuples? Code generation seems like not an option cause I need to generate new relations (list/sets/arrays/… of tuples) in runtime. It looks like impossible to get such dynamism in pure functional OCaml, doesn’t it?

This is similar to the problems that arise when defining a dataframe type in ocaml, representing rows of values as tuples. The solution that is currently used in owl for that purpose is to collect all of the unknown types into a single unified ‘wrapper’ type. This means you have to define wrapping and unwrapping functions for each of the unknown types you want to unify – i.e. there has to be a small known set of the unknown types.

Yeah it’s basically the same problem, and as far as I know there’s no static language solution that fits this well. Static languages are about knowing things beforehand, and here by definition you don’t know the type beforehand.

Could one use GADTs to model types like this?

You can use GADTs to model heterogeneous lists (aka tuples), concatenating them is also possible but hard to make user-friendly . Another possibility is to use GADTs to connect the type system of a small DSL to Ocaml’s and cast the DSL’s terms to their OCaml’s version after a runtime check.

The problem is: most relations are products of the old ones. They are unknown even for me. I need to define new types at runtime. Functors looks like an option cause they produce modules at runtime and those modules can have any types in their signatures. But I can’t express this in code. It looks like I should somehow store all the data about types but it is not how OCaml works. In dynamic languages, like Ruby it’s very easy to implement, in OCaml it’s a major issue for me.

Code generation seems like not an option cause I need to generate new relations (list/sets/arrays/… of tuples) in runtime.

Aside: some dialects of OCaml have support for run-time code generation.

To answer the question: one approach is to parameterise join by functions that extract the relevant parts and construct the result tuple. For example, here’s an implementation of join that takes three additional arguments: functions onl and onr that extract the key field from the tuples in each set, and a function merge that builds the result row:

  let (>>=) m k = List.(concat (map k m))

  let join ~onl ~onr ~merge l r =
    l >>= fun x ->
    r >>= fun y ->
    if onl x = onr y then [merge x y] else []

Then you can call join like this:

# join ~onl:fst ~onr:fst ~merge:(fun (k,x) (_,y) -> (k,x,y))
    [(1, "James"); (2, "Bob")]
    [(2, 44); (1, 34); (2, 55)];;
    - : (int * string * int) list =
[(1, "James", 34); (2, "Bob", 44); (2, "Bob", 55)]
3 Likes