Instance search is order-dependent

[yallop]

Here's an example showing how varying the order of instance bindings affects whether the search succeeds:

m.ml:

module type T = sig type 'a t type s end

implicit module T_option = struct type 'a t = 'a option type s = int end
implicit module T_list = struct type 'a t = 'a list type s = int end
implicit module T_two = struct type 'a t = 'a * 'a type s = bool end

implicit functor F (L: T) (R: T) = struct
 type 'a t = 'a L.t R.t
 type s = R.s * L.s
end

let f (implicit N: T with type s = bool * int) (v: float N.t) : unit = ()

let x = f (Some 1.0, Some 2.0)

n.ml:

module type T = sig type 'a t type s end

implicit module T_list = struct type 'a t = 'a list type s = int end
implicit module T_option = struct type 'a t = 'a option type s = int end
implicit module T_two = struct type 'a t = 'a * 'a type s = bool end

implicit functor F (L: T) (R: T) = struct
 type 'a t = 'a L.t R.t
 type s = R.s * L.s
end

let f (implicit N: T with type s = bool * int) (v: float N.t) : unit = ()

let x = f (Some 1.0, Some 2.0)

Compiling:

$ ocamlc m.ml && echo ok
File "m.ml", line 14, characters 8-9:
Error: No instance found for implicit N.
$ ocamlc n.ml && echo ok
ok
$ 

[ddanielr]

Implementation seems fine. Hashing to the hostname is what we'd like to happen for leveraging a shared cache.