www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - First experience with std.algorithm: I had to resort to writing a

reply Bernard Helyer <b.helyer gmail.com> writes:
So I'm writing a compiler, and I wanted to create a list of TokenTypes 
(an enum) and check to see if the current token is among them. 'A-ha!', 
says I, 'I'll use std.algorithm!' (as I hadn't tried it really, yet, 
except for playing around)
So I look it up, and find 'find'. It returns an iterated range, or an 
empty range on failure. A little funky, but that's okay, I can swing it!

immutable TokenType[] someList = [TokenType.Foo, TokenType.Bar];

...

while (find(someList, tokenStream.peek.type) != []) {
    doStuff();
}

If I have unittests on, this assert is triggered:

static assert(is(typeof(s) == Tuple!(string, float)));

I didn't at first, so I got another error. So I looked closer at the 
documentation, and it turns out it needs an input range, and that needs 
popFront! Well, it can't popFront an immutable range, so I dropped 
immutable, and decided to let convention and TLS sort the rest out!

This worked. Until I turned unittests on, and the assert I showed above 
tripped. At this point my language turned rather unpleasant and I wrote 
this:

bool contains(T)(const(T)[] l, T a)
{
      foreach(e; l) {
          if (a == e) {
             return true;
          }
      }
      return false;
}

And my problems went away. I assume what I experienced is a bug, but I'm 
not sure, so I thought I'd share my experience.
Jun 08 2010
next sibling parent "Lars T. Kyllingstad" <public kyllingen.NOSPAMnet> writes:
On Tue, 08 Jun 2010 23:23:39 +1200, Bernard Helyer wrote:

 [...]
 
 If I have unittests on, this assert is triggered:
 
 static assert(is(typeof(s) == Tuple!(string, float)));
 
 [...]
 
 And my problems went away. I assume what I experienced is a bug, but I'm
 not sure, so I thought I'd share my experience.
Would it be this bug, perhaps? http://d.puremagic.com/issues/show_bug.cgi?id=4294 It was just reported, following the discussion in the "Tuple to tuple conversion" thread on D.learn. It's a really annoying bug which I've come across a few times, and I'm glad Simen has been able to narrow it down so much. -Lars
Jun 08 2010
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Bernard Helyer:
 bool contains(T)(const(T)[] l, T a)
 {
       foreach(e; l) {
           if (a == e) {
              return true;
           }
       }
       return false;
 }
See also: http://d.puremagic.com/issues/show_bug.cgi?id=3923 Bye, bearophile
Jun 08 2010
next sibling parent Alex Makhotin <alex bitprox.com> writes:
bearophile wrote:
  
 See also:
 http://d.puremagic.com/issues/show_bug.cgi?id=3923
 
 Such functions must be simple enough for normal people to use. If you need more
 than 10 minutes to understand how to use something as simple as a "find", then
 the library API is badly designed. It's not a limit of my brain, it's a problem
 in the library design.
Agree. And by the way naming scheme also brings a lot of confusion, to say the least... -- Alex Makhotin, the founder of BITPROX, http://bitprox.com
Jun 08 2010
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 06/08/2010 06:59 AM, bearophile wrote:
 Bernard Helyer:
 bool contains(T)(const(T)[] l, T a)
 {
        foreach(e; l) {
            if (a == e) {
               return true;
            }
        }
        return false;
 }
See also: http://d.puremagic.com/issues/show_bug.cgi?id=3923
That issue stems from the fact that find is quite flexible. I agree it has lost modularity in the process. I'll work on restoring its modularity. Andrei
Jun 08 2010
parent reply Jonathan M Davis <jmdavisProg gmail.com> writes:
Andrei Alexandrescu wrote:

 On 06/08/2010 06:59 AM, bearophile wrote:
 Bernard Helyer:
 bool contains(T)(const(T)[] l, T a)
 {
        foreach(e; l) {
            if (a == e) {
               return true;
            }
        }
        return false;
 }
See also: http://d.puremagic.com/issues/show_bug.cgi?id=3923
That issue stems from the fact that find is quite flexible. I agree it has lost modularity in the process. I'll work on restoring its modularity. Andrei
The biggest issue is the documentation rather than the function, I think. If find() can be broken up, that could help, but the main issue is what the documentation looks like. It's just too complicated - especially the function signature. Pretty much the only sane way to figure the std.algorithm functions out is to focus on the examples (which while good are still fairly sparse). As it stands, I expect the documentation to scare away potential users of std.algorithm. It looks far scarier than it actually is. We need to find a way or ways to make the documentation simple like the functions are simple to use (since, for the most part they're pretty easy to use in spite of their nasty signatures). As for a contains() function, I would argue that it would be nice to add one regardless of the state of find(). Not only would it would make its usage clearer in the use case where you're checking whether a range contains a value, but it could almost certainly be better optimized for such a use case - if nothing else because it wouldn't have to construct a range, just return a bool. - Jonathan M Davis
Jun 08 2010
parent reply KennyTM~ <kennytm gmail.com> writes:
On Jun 9, 10 03:19, Jonathan M Davis wrote:
 Andrei Alexandrescu wrote:

 On 06/08/2010 06:59 AM, bearophile wrote:
 Bernard Helyer:
 bool contains(T)(const(T)[] l, T a)
 {
         foreach(e; l) {
             if (a == e) {
                return true;
             }
         }
         return false;
 }
See also: http://d.puremagic.com/issues/show_bug.cgi?id=3923
That issue stems from the fact that find is quite flexible. I agree it has lost modularity in the process. I'll work on restoring its modularity. Andrei
The biggest issue is the documentation rather than the function, I think. If find() can be broken up, that could help, but the main issue is what the documentation looks like. It's just too complicated - especially the function signature. Pretty much the only sane way to figure the std.algorithm functions out is to focus on the examples (which while good are still fairly sparse). As it stands, I expect the documentation to scare away potential users of std.algorithm. It looks far scarier than it actually is. We need to find a way or ways to make the documentation simple like the functions are simple to use (since, for the most part they're pretty easy to use in spite of their nasty signatures).
I agree. Especially the return type of many templated methods are so complicated that it just adds close to zero information, for example: Take!(Sequence!("a.field[0] + n * a.field[1]",Tuple!(CommonType!(B,E),uint))) iota(B, E)(B begin, E end); A better representation is auto iota(B, E)(B begin, E end); Granted, this means some information is lost when reading the signature, but no one is going to actually use the Take!(Sequence!whatever)) type directly, why bother. (There's no need to modify ddoc, just add a Javascript on the page is enough.) Another thing is the documentation feels too "crowded", in particular that crazy "navigation bar" on the top is a joke. Why can't it laid out vertically? There should be sections within a module to divide relevant functions into groups, e.g. 1. Capability checking template isInputRange(R) template isOutputRange(R,E) ... 2. Information of range size_t walkLength(Range)(Range range, size_t upTo = size_t.max); 3. Modifying ranges auto retro(R)(R input); auto stride(R)(R input, size_t n); ... 4. Constructing ranges auto recurrence(alias fun, State...)(State initial); auto iota(B, E)(B begin, E end); ...
Jun 08 2010
next sibling parent reply "Nick Sabalausky" <a a.a> writes:
"KennyTM~" <kennytm gmail.com> wrote in message 
news:hume1m$310o$1 digitalmars.com...
   Take!(Sequence!("a.field[0] + n * 
 a.field[1]",Tuple!(CommonType!(B,E),uint))) iota(B, E)(B begin, E end);

 A better representation is

   auto iota(B, E)(B begin, E end);

 Granted, this means some information is lost when reading the signature, 
 but no one is going to actually use the Take!(Sequence!whatever)) type 
 directly, why bother.
Yea, definitely agree. But, of course, there should also be an explanation of what type the caller can expect it to return, since auto is dependant on implementation and, by itself, doesn't tell the person reading the docs anything. Or maybe something like: {simple description here} iota(B, E)(B begin, E end); Example: {element type of range T} getFirstElement(T)(T range); Or: {elementTypeOfRange} getFirstElement(T)(T range); {elementTypeOfRange}: If needed, a more complete explanation goes here. I'm doing some things like that for the documentation for Goldie (The documentation's still incomplete and only in trunk though. But I'm working on it...when I have time...)
 (There's no need to modify ddoc, just add a Javascript on the page is 
 enough.)
Ugh, oh dear God, no!
Jun 08 2010
parent KennyTM~ <kennytm gmail.com> writes:
On Jun 9, 10 06:44, Nick Sabalausky wrote:
 "KennyTM~"<kennytm gmail.com>  wrote in message
 news:hume1m$310o$1 digitalmars.com...
 (There's no need to modify ddoc, just add a Javascript on the page is
 enough.)
Ugh, oh dear God, no!
Hehe. Since DDoc is bound to the spec is D2 is feature-frozen, using Javascript can be used as a workaround if DDoc cannot be changed, just like how the navigation bar is generated.
Jun 08 2010
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 06/08/2010 04:51 PM, KennyTM~ wrote:
 A better representation is

 auto iota(B, E)(B begin, E end);
FWIW that's how I first defined it. At that time ddoc had a bug that made all auto functions invisible. I think that has been fixed since. Andrei
Jun 08 2010
parent Don <nospam nospam.com> writes:
Andrei Alexandrescu wrote:
 On 06/08/2010 04:51 PM, KennyTM~ wrote:
 A better representation is

 auto iota(B, E)(B begin, E end);
FWIW that's how I first defined it. At that time ddoc had a bug that made all auto functions invisible. I think that has been fixed since. Andrei
bug 2581. Not fixed yet.
Jun 08 2010
prev sibling next sibling parent reply Alex Makhotin <alex bitprox.com> writes:
Bernard Helyer wrote:
 
 This worked. Until I turned unittests on, and the assert I showed above 
 tripped. At this point my language turned rather unpleasant and I wrote 
 this:
 
 bool contains(T)(const(T)[] l, T a)
 {
      foreach(e; l) {
          if (a == e) {
             return true;
          }
      }
      return false;
 }
 
 And my problems went away. I assume what I experienced is a bug, but I'm 
 not sure, so I thought I'd share my experience.
I want you to know that you are not the only one who makes such decisions. I have almost the same method, except it returns an index value. That is not the only one reason I wanted a std library with clear and documented interfaces. Generally I use std library to make writeln, thread wrapper around OS, and string conversions. I do not want to use std.algorithm. -- Alex Makhotin, the founder of BITPROX, http://bitprox.com
Jun 08 2010
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 06/08/2010 08:31 AM, Alex Makhotin wrote:
 Bernard Helyer wrote:
 This worked. Until I turned unittests on, and the assert I showed
 above tripped. At this point my language turned rather unpleasant and
 I wrote this:

 bool contains(T)(const(T)[] l, T a)
 {
 foreach(e; l) {
 if (a == e) {
 return true;
 }
 }
 return false;
 }

 And my problems went away. I assume what I experienced is a bug, but
 I'm not sure, so I thought I'd share my experience.
I want you to know that you are not the only one who makes such decisions. I have almost the same method, except it returns an index value. That is not the only one reason I wanted a std library with clear and documented interfaces. Generally I use std library to make writeln, thread wrapper around OS, and string conversions. I do not want to use std.algorithm.
If you could frame that as a requirement, I'd be glad to look into improving std.algorithm. (BTW. std.algorithm has had indexOf for a while, I haven't checked in that yet.) Andrei
Jun 08 2010
prev sibling next sibling parent "Lars T. Kyllingstad" <public kyllingen.NOSPAMnet> writes:
On Tue, 08 Jun 2010 23:23:39 +1200, Bernard Helyer wrote:

 [...]
 
 immutable TokenType[] someList = [TokenType.Foo, TokenType.Bar];
 
 ...
 
 while (find(someList, tokenStream.peek.type) != []) {
     doStuff();
 }
 
 If I have unittests on, this assert is triggered:
 
 static assert(is(typeof(s) == Tuple!(string, float)));
 
 I didn't at first, so I got another error. So I looked closer at the
 documentation, and it turns out it needs an input range, and that needs
 popFront! Well, it can't popFront an immutable range, so I dropped
 immutable, and decided to let convention and TLS sort the rest out!
Actually, there is no reason this shouldn't be possible. This works: import std.array: popFront; immutable(int)[] tail(immutable(int)[] list) { list.popFront(); return list; } void main() { immutable a = [0, 1, 2, 3]; assert (tail(a) == [1, 2, 3]); } The problem is that find()'s parameters are templated, so when you give it an immutable(int[]), it doesn't know it's safe to treat it as an immutable(int)[]. find() should probably be improved to allow this. I'm sure this won't be the last time someone tries to search an immutable array. -Lars
Jun 08 2010
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 08 Jun 2010 07:23:39 -0400, Bernard Helyer <b.helyer gmail.com>  
wrote:

 So I'm writing a compiler, and I wanted to create a list of TokenTypes  
 (an enum) and check to see if the current token is among them. 'A-ha!',  
 says I, 'I'll use std.algorithm!' (as I hadn't tried it really, yet,  
 except for playing around)
 So I look it up, and find 'find'. It returns an iterated range, or an  
 empty range on failure. A little funky, but that's okay, I can swing it!

 immutable TokenType[] someList = [TokenType.Foo, TokenType.Bar];

 ...

 while (find(someList, tokenStream.peek.type) != []) {
     doStuff();
 }

 If I have unittests on, this assert is triggered:

 static assert(is(typeof(s) == Tuple!(string, float)));

 I didn't at first, so I got another error. So I looked closer at the  
 documentation, and it turns out it needs an input range, and that needs  
 popFront! Well, it can't popFront an immutable range, so I dropped  
 immutable, and decided to let convention and TLS sort the rest out!
This should be filed as a bug. find should be able to strip the immutable part from the array length itself since immutable T[] implicitly casts to immutable(T)[]. I think this should be special cased. For custom ranges, it's not as easy, but array should be supported as well as is possible.
 This worked. Until I turned unittests on, and the assert I showed above  
 tripped. At this point my language turned rather unpleasant and I wrote  
 this:

 bool contains(T)(const(T)[] l, T a)
 {
       foreach(e; l) {
           if (a == e) {
              return true;
           }
       }
       return false;
 }

 And my problems went away. I assume what I experienced is a bug, but I'm  
 not sure, so I thought I'd share my experience.
As D2 nears release, and is used more and more, I'm sure we will find many problems. It's sort of a chicken-and-egg thing, people don't want to use D2 because it's changing so much, but when nobody uses it, nobody finds any bugs until it's finalized! I suspect at least one more change to const is necessary to take away the pain :) -Steve
Jun 08 2010
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 06/08/2010 08:45 AM, Steven Schveighoffer wrote:
 On Tue, 08 Jun 2010 07:23:39 -0400, Bernard Helyer <b.helyer gmail.com>
 wrote:

 So I'm writing a compiler, and I wanted to create a list of TokenTypes
 (an enum) and check to see if the current token is among them.
 'A-ha!', says I, 'I'll use std.algorithm!' (as I hadn't tried it
 really, yet, except for playing around)
 So I look it up, and find 'find'. It returns an iterated range, or an
 empty range on failure. A little funky, but that's okay, I can swing it!

 immutable TokenType[] someList = [TokenType.Foo, TokenType.Bar];

 ...

 while (find(someList, tokenStream.peek.type) != []) {
 doStuff();
 }

 If I have unittests on, this assert is triggered:

 static assert(is(typeof(s) == Tuple!(string, float)));

 I didn't at first, so I got another error. So I looked closer at the
 documentation, and it turns out it needs an input range, and that
 needs popFront! Well, it can't popFront an immutable range, so I
 dropped immutable, and decided to let convention and TLS sort the rest
 out!
This should be filed as a bug. find should be able to strip the immutable part from the array length itself since immutable T[] implicitly casts to immutable(T)[]. I think this should be special cased. For custom ranges, it's not as easy, but array should be supported as well as is possible.
I agree. Someone please file this so it doesn't fall through the cracks. Andrei
Jun 08 2010