Re: [Caml-list] two unrelated questions

[Brian Rogoff <bpr@best.com>]

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