From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id 8832D7EEB4 for ; Wed, 6 Feb 2013 10:56:34 +0100 (CET) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of gabriel.scherer@gmail.com) identity=pra; client-ip=209.85.214.53; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of gabriel.scherer@gmail.com designates 209.85.214.53 as permitted sender) identity=mailfrom; client-ip=209.85.214.53; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-bk0-f53.google.com) identity=helo; client-ip=209.85.214.53; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="postmaster@mail-bk0-f53.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AsABAB8oElHRVdY1kGdsb2JhbABFrVySYQgWDgEBAQEJCQ0HFAQjgh8BAQQBJxkBGxILAQMBCwYFCw0NISEBAREBBQEKEgYTEgKHagEDCQYMnGuMNIJ7hGEKGScDClmIdwEFDIwKhUUDlEmBWIEdiiKDMRYphCI X-IPAS-Result: AsABAB8oElHRVdY1kGdsb2JhbABFrVySYQgWDgEBAQEJCQ0HFAQjgh8BAQQBJxkBGxILAQMBCwYFCw0NISEBAREBBQEKEgYTEgKHagEDCQYMnGuMNIJ7hGEKGScDClmIdwEFDIwKhUUDlEmBWIEdiiKDMRYphCI X-IronPort-AV: E=Sophos;i="4.84,614,1355094000"; d="scan'208";a="1232624" Received: from mail-bk0-f53.google.com ([209.85.214.53]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 06 Feb 2013 10:50:32 +0100 Received: by mail-bk0-f53.google.com with SMTP id j10so525060bkw.40 for ; Wed, 06 Feb 2013 01:56:33 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=x-received:mime-version:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; bh=uSCzQTvFRMW1G3r8yVR1w0crQru386nRDlG3LZW/g2s=; b=ebrAXI4VRflTm1nuAHLv3KQnmfnle7PCjKMs5g0XYI0OL9VsQNp/cTSsAR/rMNta2M gHkQuxsP2Bk1DBC8z2+dx6AqJ4aeKVXVKwtJZz6BycZhYaT4hFMnUqMOLZef+8+kGx+H NdDx5HtjIEtk0c/TvrRqcbJ0WM0yV5j3kLkaAAHWc5OQmQUP5i38laLm/+lzadQ657+E E9W5M5pVrs9gWh6v26pT7WXyFNBRD85gKviZ5hxrZsxlgsPfyNeONmP98kDkFpudNO/f IPaQxoAMA60RR2TTDhz2/upWgllT/+enwKLVanbUmhAIxD/mFiQ0UVPIsxLNV+jzdIQc rJAw== X-Received: by 10.204.145.86 with SMTP id c22mr7604162bkv.5.1360144593072; Wed, 06 Feb 2013 01:56:33 -0800 (PST) MIME-Version: 1.0 Received: by 10.205.83.144 with HTTP; Wed, 6 Feb 2013 01:55:52 -0800 (PST) In-Reply-To: References: From: Gabriel Scherer Date: Wed, 6 Feb 2013 10:55:52 +0100 Message-ID: To: Christophe Papazian Cc: Caml List Content-Type: text/plain; charset=ISO-8859-1 Subject: Re: [Caml-list] Memoize GADT On Wed, Feb 6, 2013 at 9:19 AM, Christophe Papazian wrote: > this must be a very basic question for some of you, sorry for the inconvenience : This is actually a rather advanced question (everything related to GADTs is advanced for now, and when you add observationally pure effects and value restriction into the mix, you're quite sure this is not "very basic"), thank you for asking it. I think one important difficulty is that you want to memoize a polymorphic function, with possibly non-regular recursion: the "keys" of the memo table could have different types, and arbitrarily many so -- this can happen with polymorphic recursion, even without GADTs. It would help to see a real code example of your GADT definition and the function you're trying to memoize (for example, if it is recursive, would it be ok to just memoize over the recursive calls of a single top call, or do you also need to memoize over several unrelated calls?). I would try to do this using existential types: have an additional GADT `a tyrepr` that represents (as runtime data) the types that can be picked by the parameter `a`, then define an monomorphic existential type `exists a . a tyrepr * a gadt` (... as a third GADT type), and do your memoization on that. In the function you want to memoize you can build the existential corresponding to the argument, look it up on the table, and if you find something extract the attached value. You get a result of the type (encoded as a GADT) `exists a . a tyrepr * a result`, can check that the two type representation are equal (`a tyrepr -> b tyrepr -> (a, b) eq option`), and in this case extract your result with static knowledge that it has the right type. There have been some questions on that in the Haskell community as well, see Conal Elliott's http://conal.net/blog/posts/memoizing-polymorphic-functions-part-one and later posts (by him, Dan Piponi, and him again). > When I have function "f" of type (a -> b), I can easily add a layer to that function to memoize the result by using a (a,b) Hashtbl.t to store the results of the expensive to compute "f". > > let mf = let e = Hashtbl.create 0 in ( fun x -> try Hashtbl.find e x with Not_found -> let res = f x in Hashtbl.add e x res; res ) > > But now, I have a function "g" > let g (type a) : a gadt -> a = .... > > And If I apply the same method, type a becomes weak (_'a). > > Is there something simple to memoize that function as easy as the previous example and keep its polymorphism ? I think not, but I hope to be wrong. > > Thanks > > Christophe > > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa.inria.fr/sympa/arc/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs