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

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

[Krishnaswami, Neel]

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

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

[Pixel]

"Krishnaswami, Neel" <neelk@cswcasa.com> writes:

> 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. 

I'd say functional languages do not have to rely on iterators (using
fold/iter/...), and so decide they are not needed :)

Below is your zipfold with OO-iterator. Would there be any pb having the base
library functions based on iterators? (speed?)


let rec it_fold f init it =
  if it#is_end then init
  else 
    let v = it#value in
    it#next ; 
    it_fold f (f v init) it

let rec zipfold f init it1 it2 =
  if it1#is_end || it2#is_end then init
  else 
    let v1, v2 = it1#value, it2#value in
    it1#next ; it2#next ;
    zipfold f (f v1 v2 init) it1 it2


and here are some iterators:


class ['a] list_iterator l =
    object
      val mutable it = (l : 'a list)
      method is_end = it = []
      method value = List.hd it
      method next = it <- List.tl it
    end


type 'a btree = Empty | Node of 'a * 'a btree * 'a btree
let leaf e = Node(e,Empty,Empty)


class ['a] btree_iterator__depth_first tree =
  let rec down_the_tree up = function
    | Node(e, left, right) -> down_the_tree ((e, right) :: up) left
    | Empty -> up
  in
  object
    val mutable it = down_the_tree [] (tree : 'a btree)
    method is_end = it = []
    method value = fst (List.hd it)
    method next = 
      it <- 
	match it with
	| [] -> failwith "no next"
	| (_, Empty) :: up -> up
	| (_, node) :: up -> down_the_tree up node
  end


class ['a] btree_iterator tree =
  object
    val mutable it = [(tree : 'a btree)]
    method is_end = it = []
    method value =
      match it with
      | Node(e,_,_) :: _ -> e
      | _ -> failwith "no value"
    method next = 
      let tree2l tree = if tree = Empty then [] else [tree] in
      it <- 
	match it with
	| Node(_, left, right) :: up -> tree2l left @ tree2l right @ up
	| _ -> failwith "no next"
  end
-------------------
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