Comparing two things of any two types, in pure OCaml
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20060909 (06:37) 
From:  oleg@p... 
Subject:  Comparing two things of any two types, in pure OCaml 
This message shows an example of an open, extensible comparison function 'a > 'b > bool. Diego Olivier Fernandez Pons wrote about a help system associating (by means of a hashtable) a documentation string to a function. Alas, the hash function is not perfect and collisions are possible. Therefore, we need to validate each hashtable hit by physically (==) comparing the function (whose documentation we need to lookup) against the target function. The functions to document have generally different types. This raises two questions: how to store functions of different types in the same data structure, and how to compare a candidate function against these functions of different types. The physical comparison function (==) cannot be used as it is: we need a comparison function [cmp : 'a > 'b > bool] that can take arguments of any two types, returning false if the argument types are different. Jacques Garrigue suggested using Obj.repr. He also wrote ``Type theoretician answer: What you would need to do that transparently inside the type system is generic functions with dynamics.'' and mentioned GADT. It seems however that open polymorphic variants are ideal for the task. We start with let myeq (x : [>]) (y : [>]) = false;; and add one clause, comparing two booleans let myeq x y = match (x,y) with (`T'bool x, `T'bool y) > x = y  _ > myeq x y;; We can add another clause, for int>bool functions: let myeq x y = match (x,y) with (`T'int2bool (x : int>bool), `T'int2bool y) > x == y  _ > myeq x y;; Let's generate some test data let v1 = true let v2 x = not x let v3 f = f 2 let v4 x = x = 1;; and we are ready for the first test: let t1 = [ myeq (`T'bool v1) (`T'bool v1); myeq (`T'int2bool v4) (`T'int2bool v4); myeq (`T'bool v1) (`T'int2bool v4) ];; which gives val t1 : bool list = [true; true; false] Let us extend myeq once again: let myeq x y = match (x,y) with (`T'int2bool'2bool (x : (int>bool)>bool), `T'int2bool'2bool y) > x == y  _ > myeq x y;; We can now write the table associating with each function a documentation string. We use an associative list of sorts: let docs = [(myeq (`T'bool v1), "bool value"); (myeq (`T'int2bool v4), "v4"); (myeq (`T'int2bool'2bool v3), "v3"); ];; let lookup x docs = let rec loop = function [] > None  ((c,d)::t) > if c x then Some d else loop t in loop docs ;; Another test: let t2 = [lookup (`T'int2bool'2bool v3) docs; lookup (`T'bool v1) docs; lookup (`T'int2bool v4) docs ];; which evaluates to val t2 : string option list = [Some "v3"; Some "bool value"; Some "v4"] We realize that we forgot about the function v2, which is of the type bool>bool. So, we extend myeq once again let myeq x y = match (x,y) with (`T'bool2bool (x : bool>bool), `T'bool2bool y) > x == y  _ > myeq x y;; and extend our documentation let docs = (myeq (`T'bool2bool v2), "negation") :: docs;; let t3 = [lookup (`T'int2bool'2bool v3) docs; lookup (`T'bool2bool v2) docs; lookup (`T'bool v1) docs; lookup (`T'int2bool v4) docs ];; which evaluates to val t3 : string option list = [Some "v3"; Some "negation"; Some "bool value"; Some "v4"]