How to "merge" unknown tuples?

Learning
,
1

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?

2

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.

3

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.

4

Could one use GADTs to model types like this?

5

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.

6

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.

7

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)]
4 Likes