www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.dtl - enumerations/sequences

reply Ben Hinkle <bhinkle4 juno.com> writes:
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.
Aug 05 2004
next sibling parent "Bent Rasmussen" <exo bent-rasmussen.info> writes:
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)
{
}
Aug 06 2004
prev sibling next sibling parent reply Ben Hinkle <bhinkle4 juno.com> writes:
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
Aug 06 2004
parent "Bent Rasmussen" <exo bent-rasmussen.info> writes:
 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
Aug 06 2004
prev sibling parent reply Sean Kelly <sean f4.ca> writes:
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
Aug 06 2004
parent "Ben Hinkle" <bhinkle mathworks.com> writes:
"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.
Aug 06 2004