From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id q299M4S4029970 for ; Fri, 9 Mar 2012 10:22:04 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ArgBAFrLWU9KfVI0kGdsb2JhbABDtTMIIgEBAQEJCQ0HFAQjggoBAQEEAQIPAhMZARsRDAEDDAYFCw0uIQEBBQwBBQEcBhMbB4doC50ECot0gnGFGD+IdAEBBAuJLYceBJMggiiLJIMYPYQF X-IronPort-AV: E=Sophos;i="4.73,557,1325458800"; d="scan'208";a="148391852" Received: from mail-ww0-f52.google.com ([74.125.82.52]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 09 Mar 2012 10:21:55 +0100 Received: by wgbgn7 with SMTP id gn7so1551011wgb.9 for ; Fri, 09 Mar 2012 01:21:55 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type:content-transfer-encoding; bh=iVNk+IJYWHQs1LW9N9I+RNPn15+S1DnD+EZJcZhevQ0=; b=d+LHfNjx0EDHvLkgUEALV3+sAXpy6piuSiB1HaCc4PEo+IEOTUL6QybwPqmShnpWsD EVJR4UWmLY+0AJ1fOez4LuEhSL8/HkqOlt/Pk92t/7pm1LzFvbzOsTR/aZLj2b7O/BrO XkKlT1T6CZfIbCADE57Kdo/fh9azkUlN3J0etPxqG7ieTsdMbwiEamxY+FlJX1Z+8ec1 c2PqNu2ixJ2TpY/bR9zXzGT6ht99g30AmkFcxQ8563Cn7g9h57jyDtNF0UoIDDaChkeQ h097Whul++qzFDLv9grRdhsys80aJ3oiAGtA4xUfGNBa+0TRjeJq3f8LN7MZQEjvOWVY Eoeg== Received: by 10.180.82.132 with SMTP id i4mr2936190wiy.12.1331284915297; Fri, 09 Mar 2012 01:21:55 -0800 (PST) MIME-Version: 1.0 Received: by 10.227.200.85 with HTTP; Fri, 9 Mar 2012 01:21:15 -0800 (PST) In-Reply-To: <87mx7qz001.fsf@frosties.localnet> References: <87sjhktqwi.fsf@frosties.localnet> <4F5777F2.2000806@gmail.com> <878vjctlr3.fsf@frosties.localnet> <877gyv7k2t.fsf@frosties.localnet> <87mx7qz001.fsf@frosties.localnet> From: Gabriel Scherer Date: Fri, 9 Mar 2012 10:21:15 +0100 Message-ID: To: Goswin von Brederlow Cc: caml-list@inria.fr Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id q299M4S4029970 Subject: Re: [Caml-list] Can one implement greedy/inline data structures in ocaml? 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. 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