From: Christian Szegedy <szegedy@...>
Date: 2002-09-23T21:15:41+09:00
Subject: Re: Teach me about yield

Joseph Benik wrote:

> when do you use yield?  has it solved problems for you when you
> couldn't find another solution?  how did you first start using yield?

No, but it makes life sometimes much simpler. (After all
you could solve everything in machine code also...)

Assume that you have some data structure (e.g. a list,a tree,
a database,a string, a chessboard, whatever)
and you want to allow clients to iterate over its elements
(list entries, tree entries, database entries,
characters of the string, lines of the string, pieces on the
chess board,...).

In C, C++ or Java you would use either

1) Function pointer
2) Iterator Object
3) Cursor Object.

Example:

You want to iterate over a list (For simplicity, I took list,
but you typically have some much more complicated container class.)

*****************************************************************
Solution 1) With function pointer:

You could write in C:

void List_Iter(List_t list,
                void (*apply)(void *obj,va_list args),
                ...)
{
    va_list args;
    /** blah blah */
    va_start(apply,args);
    for ( /** blah blah */ )
    {
       apply(obj,args);
    }
    va_end(args);
}

Usage:
   a) For each iteration,
      you have to define a new iterator function
      you are passing List_Iter.

Drawback:
   a) You have to write **A LOT OF** code.
   b) The va_list is nasty (no type checking!)
      (You can use a void * context instead, but it has
       the same problem.)


*****************************************************************
Solution 2) Apply class;

You write

class List_Applier
{
    public:
    virtual void call(void *obj)=0;
};

class List
{
    public:
    // Lot of blah blah...
    void iter(List_applier &apply)
    {
       // Blah Blah
       for( /* blah blah */ )
       {
          apply.call(obj);
       }
    }
};

Usage: For each iteration you have to introduce a
        new class, override the call method.

Advatage: (to solution 1)): Type safe: no nasty va_list, (or
            void * context).

Drawback: Even **MORE** lines of code than solution 1).
           You have to write about 20 lines for a very
           simple iteration!

*****************************************************************

Solution 3) Cursor. (In C++:)

class List
{
    public:
       class Cursor
       {
           List::Entry *entry;
           public:

           Cursor(List &list)
           {
              // Blah blah
           }
  	
           void next()
           {
              /** Blah blah */
           }

           bool valid()
           {
              return (entry!=(List::Entry*)0);
           }
       };
};

Usage :
You write
    for( Cursor cur(list); cur.valid() ; cur.next()
    {
        // DO something...
    }

Advantage (to 1) 2)) **Much** less work to use. (Only 1 line instead of 
about 20).

Drawbacks: (Still, it is too much for a simple iteration.)
            a) **A LOT_OF code** to write the iterator. (A new
               class and 3 new methods)
            b) There is **no** standard way in the language: you have
               to remember the way how to iterate over your particular
               data structure.
            c) It is not always simple to iterate over a data structure
                by using cursor and next (e.g. you would implement
                an iterator over a tree by a recursive function.)


*****************************************************************

Solution 4):
The Ruby way  (via yield, simply linked list):
(A complete implemenatation for a change):

Example A):

class List
   def add(obj)
     @first = [@first,obj]
   end

   def each
     e = @first
     while e
       yield e[1]
       e = e[0]
     end
   end
end

l = List.new

l.add("hello")
l.add("world")

l.each do |s|
   puts s
end

The yield in the "each" function calls the block for each object of
the list. The example above prints:
hello
world

Drawbacks: none.

-------------------------------------------------------------
Example B): Traversing a data structure recursively:

class Array
   def traverse_rec
     for e in self do
       if e.kind_of? Array
         e.traverse_rec
       else
         yield e
       end
     end
   end
end

[ [1,2] [1,3,[4,[5] ],2,[3,4] ] ].traverse_rec do |el|
    puts el;
end

outputs all elementes of the tree recursively.
(The tree is implemented as an array of (possible arrays of
  (possible ....))... )

------------------------------------------------------------
Example C)

Do something with each element of the a data structure
(minor variation of example 1):

class List
   def add(obj)
     @first = [@first,obj]
   end

   def map
     e = @first
     while e
       e[1] = yield e[1]
     end
   end
end

l = List.new

l.add("hello")
l.add("world")

l.map do |s|
   s.length
end

Each element of the list is replaced by its length.


-------------------------------------------------------------
Example D)

Do something according to a dynamic criterion

(Sum up all elements of a list conditionally)

class List
   def add(*objs)
     objs.each do |obj|
        @first = [@first,obj]
     end
   end

   def sum_if
     e = @first
     sum = 0;
     while e
       sum += e[1] if yield e[1]
     end
   end
end

l = List.new
l.add(1,3,4,5,6,2,1,6);

l.add_if do |i|
   (i%3)==0
end

The last function sums all elements of the list which
are divisible by 3.


I hope it gives you some insides about the power
of yield.

Regards, Christian