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