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 TAA22998; Fri, 9 Nov 2001 19:44:01 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA23665 for ; Fri, 9 Nov 2001 19:44:00 +0100 (MET) Received: from smtp2.cswv.com (smtp2.cswv.com [4.17.129.20]) by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id fA9Ihx514846 for ; Fri, 9 Nov 2001 19:44:00 +0100 (MET) Received: from smtp2.cswv.com ([10.2.3.6]) by smtp2.cswv.com with Microsoft SMTPSVC(5.5.1877.197.19); Fri, 9 Nov 2001 13:43:53 -0500 Received: FROM exchange1.cswv.com BY smtp2.cswv.com ; Fri Nov 09 13:43:52 2001 -0500 Received: by exchange1.cswv.com with Internet Mail Service (5.5.2653.19) id ; Fri, 9 Nov 2001 13:48:27 -0500 Message-ID: From: "Krishnaswami, Neel" To: Caml Subject: Re: [Caml-list] From folds to zips (was Dynamic vs. Static) Date: Fri, 9 Nov 2001 13:48:27 -0500 MIME-Version: 1.0 X-Mailer: Internet Mail Service (5.5.2653.19) Content-Type: text/plain; charset="iso-8859-1" Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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