Rust switches to external iteration

[Artur Skawina]

On 07/04/13 20:27, bearophile wrote:
> Having a built-in "yield" in a language is quite handy. Take a look at the Python and the second D solutions here:
> http://rosettacode.org/wiki/Same_Fringe

Would tuples really be the ideal tree representation when dealing
with mutable data in /real/ code?

Anyway, let's see... Right now, D will let you do this:

   struct Fringe(T) {
      struct State { T* root; HeapRange!Fringe subtree; };
      mixin GeneratorT!(State, q{
            if (root.l) 
               for (subtree = Fringe(root.l); !subtree.empty; subtree.popFront() )
                  yield subtree.front;
            if (root.isLeaf())
               yield root.v;
            if (root.r)
               for (subtree = Fringe(root.r); !subtree.empty; subtree.popFront() )
                  yield subtree.front;
         }, typeof(T.v));
   }
   Fringe!TREE fringe(TREE)(TREE* tree) { return Fringe!TREE(tree); }

   auto sameFringe(R1, R2)(R1 r1, R2 r2) {
      import std.algorithm : equal; return equal(fringe(r1), fringe(r2));
   }

   void fringetest() {
      auto t1 = tree(tree(tree(1), 2, tree(3)), 4, tree(tree(5), 6, tree(7)));
      auto t2 = tree(tree(tree(1), 8, tree(3)), 9, tree(tree(5), 0, tree(7)));
      auto t3 = tree(tree(tree(1), 2, tree(3)), 4, tree(tree(5), 6, tree(8)));
      auto t4 = tree(tree(tree(1), 2, tree(3)), 4, tree(tree(5), 6, tree(null, 8, tree(7))));
      
      assert(sameFringe(t1, t2));
      assert(!sameFringe(t1, t3));
      assert(sameFringe(t1, t4));
   }

It really can't be made much simpler, it's just a few extra characters
of boilerplate. Modulo certain other language issues, like no IFTI on
constructors, and an imperfect compiler (the explicit "typeof(T.v)" is
only required to work around forward ref errors)

The problem with encouraging this style is that people will use this approach,
and then not expose the other range properties. It will result in less 
efficient code, which is harder and more bug-prone to improve (because the
internal state has to be handled too).

Having input ranges be as simple to define as:

   auto iota(T)(T start, T end) {
      struct State { T start, end, i; }
      return Generator!(State, q{
                           for (i=start; i<end; ++i)
                              yield state.i;
                        })
                        (start, end);
   }

   auto map(alias F, R)(R r) {
      struct State { R r; alias F MF; }
      return Generator!(State, q{
                           for(; !r.empty; r.popFront())
                              yield MF(r.front);
                        })
                        (r);
   }

is nice, but has downsides. A DSL like this one is probably enough,
there's not that much to gain from adding "yield" to the core language. [1]

artur

[1] A bit compiler support would make it /safer/, though; right now it's
    too easy to lose part of the state. But having implicit allocations
    (closure-like) wouldn't be a good solution; better diagnostics might
    be enough.