From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <daniel.buenzli@erratique.ch>
Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83])
	by sympa.inria.fr (Postfix) with ESMTPS id 951EA7FC86
	for <caml-list@sympa.inria.fr>; Thu, 19 Mar 2015 11:45:40 +0100 (CET)
Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender
  authenticity information available from domain of
  daniel.buenzli@erratique.ch) identity=pra;
  client-ip=74.55.86.74;
  receiver=mail2-smtp-roc.national.inria.fr;
  envelope-from="daniel.buenzli@erratique.ch";
  x-sender="daniel.buenzli@erratique.ch";
  x-conformance=sidf_compatible
Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender
  authenticity information available from domain of
  daniel.buenzli@erratique.ch) identity=mailfrom;
  client-ip=74.55.86.74;
  receiver=mail2-smtp-roc.national.inria.fr;
  envelope-from="daniel.buenzli@erratique.ch";
  x-sender="daniel.buenzli@erratique.ch";
  x-conformance=sidf_compatible
Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender
  authenticity information available from domain of
  postmaster@smtp.webfaction.com) identity=helo;
  client-ip=74.55.86.74;
  receiver=mail2-smtp-roc.national.inria.fr;
  envelope-from="daniel.buenzli@erratique.ch";
  x-sender="postmaster@smtp.webfaction.com";
  x-conformance=sidf_compatible
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: A0A1AAAHqApVm0pWN0pcg1hagw3DB4V1AoIVAQEBAQEBEQEBAQEBBgsLCRQuhBABBAEjBFIFCwsaAiYCAkcQBhuIHwgECbFRm3sBAQEHAQEBAR6BIYl2gmGBXTMHgmgvgRYFlDeHGjqFHw+JXoNHhBFuAQEBgkABAQE
X-IPAS-Result: A0A1AAAHqApVm0pWN0pcg1hagw3DB4V1AoIVAQEBAQEBEQEBAQEBBgsLCRQuhBABBAEjBFIFCwsaAiYCAkcQBhuIHwgECbFRm3sBAQEHAQEBAR6BIYl2gmGBXTMHgmgvgRYFlDeHGjqFHw+JXoNHhBFuAQEBgkABAQE
X-IronPort-AV: E=Sophos;i="5.11,429,1422918000"; 
   d="scan'208";a="126723742"
Received: from mail6.webfaction.com (HELO smtp.webfaction.com) ([74.55.86.74])
  by mail2-smtp-roc.national.inria.fr with ESMTP; 19 Mar 2015 11:45:39 +0100
Received: from [172.20.10.2] (27.233.197.178.dynamic.wless.lssmb00p-cgnat.res.cust.swisscom.ch [178.197.233.27])
	by smtp.webfaction.com (Postfix) with ESMTP id E75B120F0C34;
	Thu, 19 Mar 2015 10:44:48 +0000 (UTC)
Date: Thu, 19 Mar 2015 11:44:46 +0100
From: =?utf-8?Q?Daniel_B=C3=BCnzli?= <daniel.buenzli@erratique.ch>
To: =?utf-8?Q?Milan_Stanojevi=C4=87?= <milanst@gmail.com>
Cc: Caml-list <caml-list@inria.fr>
Message-ID: <A9833AA6DB2C40058D2E66B6A381E599@erratique.ch>
In-Reply-To: <CAKR7PS_fFML9gvqF1Zr0qa+2uEMUg4FQfp2f9gXuhN1Ee7_n=A@mail.gmail.com>
References: <2AB388B4D07D4DDABA30298A7C890319@erratique.ch>
 <CAKR7PS_K5A5XR0nDnMv4z23LjxGBoi299vKY3+fccd1HuSEM-A@mail.gmail.com>
 <596DAEC11B474882835CEA10AAACE35E@erratique.ch>
 <CAKR7PS_fFML9gvqF1Zr0qa+2uEMUg4FQfp2f9gXuhN1Ee7_n=A@mail.gmail.com>
X-Mailer: sparrow 1.6.4 (build 1178)
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
Subject: Re: [Caml-list] GADT existential escape

Le jeudi, 19 mars 2015 =C3=A0 02:27, Milan Stanojevi=C4=87 a =C3=A9crit :
> This is doable in OCaml.

Cool, a new trick. My understanding of this is basically to apply to types =
the same idea as Univ by representing them as a first class module.=20=20

However are you sure your example compiles (tried to check, but Core fails =
on me in the toplevel) ? Trying the following [1] self-contained implementa=
tion of the idea [1] the compiler still complains about escaping types.=20=
=20

> Note that Univ was possible in OCaml even before first-class
> modules, GADTs and extensible types (which are all used in Type_equal)

Yes, see http://alan.petitepomme.net/cwn/2010.02.09.html#1 if you are inter=
ested how.=20=20

Thanks,

Daniel

[1]

module Key =3D struct
  type _ t =3D ..
end

module type W =3D sig
  type t
  type _ Key.t +=3D Key : t Key.t
end

type 'a witness =3D (module W with type t =3D 'a)

let witness () (type s) =3D
 let module M =3D struct
   type t =3D s
   type _ Key.t +=3D Key : t Key.t
 end
 in
 (module M : W with type t =3D s)

type ('a, 'b) eq =3D Eq : ('a, 'a) eq

let eq (type r) (type s) (r : r witness) (s : s witness)
  : (r, s) eq option
  =3D
  let module R =3D (val r : W with type t =3D r) in
  let module S =3D (val s : W with type t =3D s) in
  match R.Key with
  | S.Key -> Some Eq
  | _ -> None

type 'a key =3D 'a witness
type binding =3D B : 'a key * 'a -> binding
type dict =3D binding list

let lookup : dict -> 'a key -> 'a option =3D fun d k ->
  let rec find =3D function
  | [] -> None
  | B (k', v) :: bs ->
      match eq k k' with
      | None -> find bs
      | Some Eq -> Some v
  in
  find d