From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id q2ACnDkn005339 for ; Sat, 10 Mar 2012 13:49:13 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AjsEAOJMW0/ZSMD3k2dsb2JhbABCtUwiAQEBAQkJFBQDJIIKAQEBAwEBAiQLAToMBQsLGAklDwEEDQcUIRMbh2oJB7ZaBIlEhz0EkyOHf4VVh1w X-IronPort-AV: E=Sophos;i="4.73,561,1325458800"; d="scan'208";a="135353572" Received: from fmmailgate06.web.de ([217.72.192.247]) by mail4-smtp-sop.national.inria.fr with ESMTP; 10 Mar 2012 13:49:08 +0100 Received: from moweb002.kundenserver.de (moweb002.kundenserver.de [172.19.20.108]) by fmmailgate06.web.de (Postfix) with ESMTP id 0772BE5F288 for ; Sat, 10 Mar 2012 13:49:08 +0100 (CET) Received: from frosties.localnet ([95.208.118.96]) by smtp.web.de (mrweb002) with ESMTPA (Nemesis) id 0LkPW7-1SceTo3Fl5-00cN0c; Sat, 10 Mar 2012 13:49:07 +0100 Received: from mrvn by frosties.localnet with local (Exim 4.77) (envelope-from ) id 1S6LjP-0002P5-7l; Sat, 10 Mar 2012 13:49:07 +0100 From: Goswin von Brederlow To: Gabriel Scherer Cc: Goswin von Brederlow , caml-list@inria.fr References: <87sjhktqwi.fsf@frosties.localnet> <4F5777F2.2000806@gmail.com> <878vjctlr3.fsf@frosties.localnet> <877gyv7k2t.fsf@frosties.localnet> <87mx7qz001.fsf@frosties.localnet> Date: Sat, 10 Mar 2012 13:49:07 +0100 In-Reply-To: (Gabriel Scherer's message of "Fri, 9 Mar 2012 10:21:15 +0100") Message-ID: <874ntwsjss.fsf@frosties.localnet> User-Agent: Gnus/5.110009 (No Gnus v0.9) XEmacs/21.4.22 (linux, no MULE) MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Provags-ID: V02:K0:db/SmUdAyRJZEWn+gVwcozWFw2tPTwUPOceGZx2zr4/ DotVMVyz2VABsWuBNnbkCVC3CMWa4NVThN6Ge8z5L1IeIY5iLw +ANNsk3wfbjakxMSRv5lzy/S90tknZ96HaBP2+ED2Z3872Q8bH HRi27EiK9P1wK56Q5ompKYIKtH11MKqkqXiy49jtvNNJVwEMQx NGOhajCVieXvfi5lSod5w== Subject: Re: [Caml-list] Can one implement greedy/inline data structures in ocaml? Gabriel Scherer writes: > I think this is a case of using a fancy new construction when a > simpler construction would do just as well. > For some reasons some people, even beginners, are absolutely fond of > first-class modules, and insist on using them in situation where > they're really not needed. I not eager to see what they will do with > GADTs... > > In your case, you could simply use ('a -> 'a dllist) instead of your > Accessor module. Your code works just fine with the following > definitions of make_accessor and get_next: > > let make_accessor f = f (* useless, for code compatibility *) > let get_next get y = (get y).next > > I think learning *not to use* fancy features is just as fun as using them. Sure. I think you missed the "For the fun of it" right at the begining. One advantage of using a first class module though is that they are extensible. I could define 2 accessor modules:    let module DList_Accessor = struct      type a = c      let get_next x = get_next x.dlist      let get_prev x = get_prev x.dlist      let set_next x = set_next x.dlist      let set_prev x = set_prev x.dlist    end    let module PrioQueue_Accessor = struct      type a = c      let get_next x = get_next x.queue      let get_prev x = get_prev x.queue      let set_next x = set_next x.queue      let set_prev x = set_prev x.queue let get_prio x = get_prio x.queue let set_prio x = set_prio x.queue    end Now any function that operates on (module DList) can also be called with (module PrioQueue). You can't do that with closures or records of closures. You can do it with objects though. Note: you probably wouldn't implement a priotity queue as doubly linked list. Just an example. > On Fri, Mar 9, 2012 at 8:50 AM, Goswin von Brederlow wrote: >> Gabriel Scherer writes: >> >>> I have implemented a small example in two versions: one with external >>> dllist (I'm using the Batteries Dllist module), which indeed needs a >>> small hack to bootstrap a single-element cycle, and one with inline >>> pointers as you show, using simple value recursion. In the second case >>> I also have a small abstraction layer for traversals -- only >>> instantiated in the 'iter' case currently -- that could save some code >>> duplication; that must be one of the "closures" tricks you were >>> thinking of, but I don't claim that it's as efficient than duplicated >>> specialized traversal functions. >>> >>> The code is here: >>>   https://gitorious.org/gasche-snippets/outside-or-inline-lists/blobs/master/goswin_dllists.ml >> >> For the fun of it I wrote a version with first class modules. It is >> pretty much like your inline solution with records of closures, just a >> different syntax. >> >> The one thing I can't eliminate is the code duplication for the >> initialization. I'm starting to believe there is no way around using >> Obj.magic or option types there. At least for the verry first task (in >> each dlist). The right-hand restriction in a let rec simply prevents >> putting that code into a function. >> >> For DList the duplication is minimal because the container is so >> simple. But for more complex container more code would have to be >> duplicated. The code could be hidden behind camlp4 though. >> >> MfG >>        Goswin >> >> ---------------------------------------------------------------------- >> >> (* Type for doubly linked list *) >> type 'a dlist = { >>  mutable next : 'a; >>  mutable prev : 'a; >> } >> >> (* Module to access a container in another type *) >> module type Accessor = sig >>  type a >>  val get : a -> a dlist >> end >> >> (* create an access module from a closure *) >> let make_accessor : 'a . ('a -> 'a dlist) -> >>  (module Accessor with type a = 'a) = >>  fun (type c) (fn : c -> c dlist) -> >>    let module M = struct >>      type a = c >>      let get x = fn x >>    end >>    in >>    (module M : Accessor with type a = c) >> >> (* Iterator over a DList *) >> let get_next : 'a . (module Accessor with type a = 'a) -> 'a -> 'a = >>  fun (type a) x y -> >>    let module D = (val x : Accessor with type a = a) >>    in >>    (D.get y).next >> >> (* Now lets use this: *) >> >> (* A task has 2 DList: all and state *) >> type task = { >>  all : task dlist; >>  state : task dlist; >>  name : string; >> } >> >> (* Accessors for the two DLists *) >> let all = make_accessor (fun task -> task.all) >> let state = make_accessor (fun task -> task.state) >> >> (* Some sample tasks *) >> let rec task1 = { >>  all = { next = task2; prev = task2; }; >>  state = { next = task1; prev = task1; }; >>  name = "task1"; >> } >> and task2 = { >>  all = { next = task1; prev = task1; }; >>  state = { next = task2; prev = task2; }; >>  name = "task2"; >> } >> >> let () = >>  Printf.printf "all_next = %s, state_next = %s \n" >>    (get_next all task1).name >>    (get_next state task1).name MfG Goswin