From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id XAA32144; Tue, 1 May 2001 23:08:58 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id XAA32447 for ; Tue, 1 May 2001 23:08:57 +0200 (MET DST) Received: from shell5.ba.best.com (shell5.ba.best.com [206.184.139.136]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id f41L8u508029 for ; Tue, 1 May 2001 23:08:56 +0200 (MET DST) Received: from localhost (bpr@localhost) by shell5.ba.best.com (8.9.3/8.9.2/best.sh) with ESMTP id OAA29479; Tue, 1 May 2001 14:08:51 -0700 (PDT) Date: Tue, 1 May 2001 14:08:50 -0700 (PDT) From: Brian Rogoff To: John Max Skaller cc: Mark Seaborn , caml-list@inria.fr Subject: Re: [Caml-list] two unrelated questions In-Reply-To: <3AE89F2E.622B7EFC@ozemail.com.au> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Fri, 27 Apr 2001, John Max Skaller wrote: > Mark Seaborn wrote: > > Another way of doing it is to CPS-convert the fold function to get > > something like: > > > > let rec foldc kons knil l = match l with > > | [] -> knil > > | x::xs -> kons x knil (fun rest -> foldc kons rest xs) > > > This is more powerful than fold, but also harder to understand, > > You're not kidding, on both counts :-) I admit, I'm a sucker for CPS tricks. They are kind of hard to follow sometimes, even for the initiated. > It's also 'ugly', because it only works for lists, > but this is only because you hard coded the destructor. > Passing it as an argument: > > let rec foldc remove kons knil l = match remove l with > | (_,None) -> knil > | (xs,Some x) -> kons x knil (fun rest -> foldc remove kons rest xs) > > let foldc_list = foldc (fun l -> match l with > | [] -> l,None > | x::xs -> xs,Some x) Yes, this is better. You can also use it with the inductive graph types defined by Martin Erwig. He names his destructor "match" (I rename it "extract" in my version of his library) and his constructor embed; the destructor takes a graph to a "context" (a node with incoming and outgoing edges) and a graph with that context removed. It also fits on to OCaml Sets nicely too. Of course, you should always remember that the value restriction sucks and that eta expansion is your friend, and write it like this ;-) let set_destruct s = if is_empty s then (s, None) else let elt = PolySet.choose s in let s' = PolySet.remove elt s in (s', Some elt) (* another case for left to right :-) *) let foldc_set kons knil l = foldc set_destruct kons knil l > It's a pity there is no such destructor for a Hashtbl. > [All C++ STL data structures have read iterators, which > amount to destructors] Are they really the same? I think of STL style iterators as being more similar to array indices, and arrays (and hashtables) are not defined inductively like lists, trees, and graphs, etc. As I'm sure you know, there is an easy enough transformation from hashtables (and arrays) to lists, like the following let pairs_of_hashtbl ht = let pl_ref = ref [] in let fn a b = (pl_ref := (a,b)::(!pl_ref) in (Hashtbl.iter fn ht; !pl_ref) which gives you a simple adaptor for folds. I think it's a pity from this POV that Map doesn't have an "is_empty" predicate and a "choose" which allow you to hand code a destructor analogous to your list destructor and the set destructor above. -- Brian ------------------- To unsubscribe, mail caml-list-request@inria.fr. Archives: http://caml.inria.fr