Re: [Caml-list] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[brogoff@speakeasy.net]

On Thu, 18 Dec 2003, Nicolas Cannasse wrote:
> > [...]
> > > This only works for simple examples. Try for example writing a
> > > function which successively yields all possible moves for a chess
> > > board. The "yield" operator really helps there.
> >
> > Very interesting: please give us the code corresponding to this
> > example, in order for us to realize how the full power of the "yield"
> > operator helps to solve this problem.
> >
> > Pierre Weis
> >
>
> One simple sample is tree walking :
> "if there was yield in ocaml"
>
> type 'a tree =
>     |  Node of 'a tree list
>     |  Leaf of 'a
>
> let rec iterator = function
>     | Node l -> List.iter iterator l
>     | Leaf x -> yield x

I think this problem is relatively easily handled by the simple home made
lazy lists I described before, available even in SML or Lisp.

The canonical problem of this class is the "same fringe" problem for trees,
where you'd like to compare the tree fringe but not have to build the entire
fringe and do all of the comparisons, but just walk the tree and bail after the
first inequality. I've appended the code of a simple polymorphic generator
module, and two different tree representations to test samefringe on. I believe
that the code is not much longer than the equivalent Sather code, if we take for
granted that the generator code is part of the library.

If this kind of stuff interests you, I suggest you also check out "zippers", and
the paper called "That About Wraps It Up" on using Y in ML programming. The
first, because the notion of "whole + context" is a useful one for traversing
and manipulating data structures in a functional style, the second because you
would like to know about simulating coroutines with first class functions.

Of course, OCaml also has support for laziness with both Lazy (an lazy) as well
as streams which offer other approaches, but I think the simple stuff buys you a
lot of what iterators do.

-- Brian

module Generator =
  struct
     type  'a t = Nil | Cons of 'a * (unit -> 'a t)

     (* Equality of two generators *)

     let rec eq lz1 lz2 =
       match (lz1,lz2) with
         Nil, Nil -> true
       | Cons (v1,f1), Cons (v2,f2) -> (v1 = v2) && eq (f1()) (f2())
       | _ -> false

     exception Empty

     let make_nil () = Nil

     let make x = Cons (x, make_nil)

    (* Combines two generators *)

     let rec concat f g =
       match f () with
         Nil -> g ()
       | Cons(x,h) -> Cons(x, fun () -> concat h g)

    (* Return the first item of the generator paired with the rest *)

     let yield : 'a t -> 'a * 'a t = function
         Nil -> raise Empty
       | Cons(x,h) -> x, (h ())
  end;;

module Tree =
  struct

    (* A generic binary tree data type
    *)
    type 'a t = Leaf of 'a | Node of 'a t list

    let make_leaf x = Leaf x
    let make l = Node l

    let rec fringe = function
        Leaf(x) -> Generator.make x
      | Node[] -> Generator.Nil
      | Node(x::xs) ->
          Generator.concat (fun () -> fringe x) (fun () -> fringe (Node xs))

    let samefringe t1 t2 = Generator.eq (fringe t1) (fringe t2)
  end;;

module BinaryTree =
  struct

    (* A generic binary tree data type
    *)
    type 'a t = Leaf of 'a | Node of 'a t * 'a t

    let make_leaf x = Leaf x
    let make l r = Node(l,r)

    let rec fringe = function
        (Leaf x) -> Generator.make x
      | (Node(l,r)) ->
          Generator.concat (fun () -> fringe l) (fun () -> fringe r);;

    let samefringe t1 t2 = Generator.eq (fringe t1) (fringe t2)
  end;;


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners