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

[Pixel <pixel@mandrakesoft.com>]

"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