Re: [Caml-list] From folds to zips (was Dynamic vs. Static)

["Krishnaswami, Neel" <neelk@cswcasa.com>]

Patrick M Doane [mailto:patrick@watson.org] wrote:
> 
> It's also worth noting that, for whatever reason, Caml does not 
> have a very good collection library. The modules indivually are 
> quite good but they lack the unification that allows a developer to 
> easily plug in a new implementation as needed.

I find that about 80% of my collection needs are handled with a
good fold definition for iterating over it. However, the remaining
20% of the time I run into a very painful problem: I don't know
how to express parallel iteration with folds. So we all know that 
an expression like:

  List.fold_left ~f:(+) ~init:0 foo 

is equivalent to a for-loop (eg, in Python) like:
 
  acc = 0
  for elt in foo:
      acc = elt + acc
  
However, the 20% of the time I need something more complicated, I would
write (in an imperative language) some code with a pattern like:

  acc = 0 
  for s, t in zip(foo, bar): # parallel creates an iterator
     acc = frob(s, t, acc)

and rely on the iteration protocol to lazily enumerate the elements
of each collection. I don't know how to write code equivalently 
generic in Caml. For specific types -- eg, lists -- there are
functions like List.fold_left2, but I don't know how to get from a 
fold to a zip for generic collections. 

That is, suppose I have two type 'a s and 'a t, with operations

val sfold : f:('a -> 'b -> 'b) -> init:'b -> 'a s -> 'b
val tfold : f:('a -> 'b -> 'b) -> init:'b -> 'a t -> 'b

How would I use them to write a function 

val zipfold : f:('a -> 'b -> 'c -> 'c) -> init:'c -> 'a s -> 'b t -> 'c

that does not do unnecessary consing? (A constant memory overhead 
is okay, but intermediate datastructures of size O(N) are not.)

--
Neel Krishnaswami
neelk@cswcasa.com
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr