I was thinking some more about polymorphic views onto containers (eg Enumerations) with an eye towards experimenting with something along those lines in MinTL. The functions in a basic Enumeration are

 interface Enumeration(Value) {
  Value next();
  bool hasNext();
 }

but this is very similar to what goes into a foreach statement. The difference between foreach and Enumeration is that the enumeration state can be "paused" at any point and picked up again. This will cause problems for a library implementation of an Enumeration for a builtin associative array since any such implementation will have to make assumptions about the private (compiler-dependent) structure of the associative array. This isn't a disaster but it is unfortunate. So I thought it wouldn't be so bad to lose this ability to pause the enumeration as long as the polymorphic aspect of the traversal is preserved. So I went and defined in MinTL two interfaces

 interface Seq(Value) {
   int opApply( int delegate(inout Value value) dg);
 }

and

 interface SeqWithKeys(Keys,Value) : Seq!(Value) {
   int opApply( int delegate(Key key, inout Value value) dg);
 }

and made implementations for each of the containers in MinTL *and* the builtin dynamic and associative arrays. For containers like lists and dynamic arrays which don't have a user-specified Key type the Key type is int (since the container is indexed by integers). This means functions that don't want to be tied to a particular container type but just want to "foreach" over a bunch of values or key-value pairs can take a sequence as input and polymorphic dispatching will make sure the right opApply is called at run-time. For example:

    // define a function that takes an arbitrary sequence of doubles
    void printItems(Seq!(double) seq) {
      foreach( double item; seq) {
        printf("%g\n",item);
      }
    }
    ...
    double[] x;
    ... // fill x
    Seq!(double) seq = toSeq!(double[])(x); // array as sequence
    printItems(seq);
    List!(double) y;
    ... // fill y
    Seq!(double) seq2 = y.toSeq; // List as sequence
    printItems(seq2);

The examples using associative arrays is similar. I think the trade-off of
losing the ability to suspend the traversals is offset by gaining "foreach"
support and builtin associative array support. What do others think?

-Ben
ps I've updated the download at http://home.comcast.net/~benhinkle/mintl/ so
that people can experiment with it.

Not getting into your design philosophy, here is an alternative iterator design

interface Map (T, S = int)
{
    int opApply (int delegate (inout T));
    int opApply (int delegate (inout S, inout T));
}

interface Seq (T) : Map!(T)
{
}

Bent Rasmussen wrote:

> Not going into the philosophy of your design, here's a possible alternative to your iteration interfaces. Seq can still be defined in terms of Map of course.
> 
> interface Map (S = int, T)
> {
>     int opApply (int delegate (S, inout T x) f);
>     int opApply (int delegate (inout T x) f);
> }

I considered only having one interface but here's my chain of logic for why
having two is better:
suppose a function foo(Map!(double) x) just wants to iterate over a sequence
of values of type double and doesn't care about any keys. Ok, no problem
the keys (S) default to int. But now someone has an associative array with
keys of type char[] so they can't pass their key-value pairs
(char[]-double) to foo. Ok, no problem there are two implementations of the
interface for associative arrays - one with int S and one with char[] S.
Let's assume this can work (I didn't even try it, actually, due to the next
thought). But then which one is chosen if the true keys are ints instead of
char[]? Hmm. That is a problem. I didn't even try testing out if D picks
one of the templates or errors. To me that ambiguity is reason enough to go
with two interfaces.

Also to me it seems cleaner/simpler to declare foo with just the information that it needs. Since all it wants are values and not keys then keys shouldn't be forced upon it.

A small question, too: shouldn't the default template parameters come last? Map(T,S=int)? I haven't tried putting them first - I assumed they had to come last.

-Ben

> A small question, too: shouldn't the default template parameters come
last?
> Map(T,S=int)? I haven't tried putting them first - I assumed they had to
> come last.

I considered that after I posted the message. I then cancelled my original message and reposted the change. :-)

> -Ben
>

In article <ceuoev$2g9f$1@digitaldaemon.com>, Ben Hinkle says...
>
>The examples using associative arrays is similar. I think the trade-off of losing the ability to suspend the traversals is offset by gaining "foreach" support and builtin associative array support. What do others think?

You don't have to lose the ability to suspend transversals.  It would be extra baggage, but the sequence for associative arrays could also hold a Key[] variable and a position and do successive lookups based on the key position.  A bit expensive perhaps, but it doesn't rely on knowledge of internals.  I suppose the other option would be both Key[] and Value[] arrays, though I haven't looked into whether the ordering is the same for both (I imagine it is).

I do like the sequence idea though, as I think it's important to be able to have adaptors for builtin containers, however they work.


Sean

"Sean Kelly" <sean@f4.ca> wrote in message news:cf07o5$hkm$1@digitaldaemon.com...
> In article <ceuoev$2g9f$1@digitaldaemon.com>, Ben Hinkle says...
> >
> >The examples using associative arrays is similar. I think the trade-off
of
> >losing the ability to suspend the traversals is offset by gaining
"foreach"
> >support and builtin associative array support. What do others think?
>
> You don't have to lose the ability to suspend transversals.  It would be
extra
> baggage, but the sequence for associative arrays could also hold a Key[] variable and a position and do successive lookups based on the key
position.  A
> bit expensive perhaps, but it doesn't rely on knowledge of internals.  I
suppose
> the other option would be both Key[] and Value[] arrays, though I haven't
looked
> into whether the ordering is the same for both (I imagine it is).

True, though I think that's too expensive to be considered for the same tasks as an Enumeration-like class.

> I do like the sequence idea though, as I think it's important to be able
to have
> adaptors for builtin containers, however they work.
>
>
> Sean
>
>

It also occurred to me that Matthew's filter templates can be (sortof) implemented as run-time sequence filters. The performance isn't as good as compile-time templates (presumably). For example here is a "transform filter" that takes a sequence and produces another sequence with a delegate applied to each item:

template transformSeq(Value) {
  Seq!(Value) transformSeq(Seq!(Value) seq, Value delegate(Value x) dg) {
    return new TransformSeqImpl!(Value)(seq,dg);
  }
}
private class TransformSeqImpl(Value) : Seq!(Value) {
  Seq!(Value) fSeq;
  Value delegate(Value x) fDelegate;
  this(Seq!(Value) seq, Value delegate(Value x) dg) {
    fSeq = seq;
    fDelegate = dg;
  }
  int opApply(int delegate(inout Value val) dg) {
    int res = 0;
    foreach( Value value; fSeq) {
      Value newvalue = fDelegate(value);
      res = dg(newvalue);
      if (res) break;
    }
    return res;
  }
}
...
Seq!(int) x;
... // fill x
Seq!(int) x2 = transformSeq!(int)(x,delegate int(int x){ return x*2; })
 // x2 will now be x with each item doubled

There isn't really anything new or D-specific about this transformSeq, though. Just something I noticed.