www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - std.algorithm - notes

reply bearophile <bearophileHUGS lycos.com> writes:
Few comments to the std.algorithm of D 2.0 by Andrei Alexandrescu:

- Generally this module seems rich of many useful things. Tons of things I have
written become little useful with this library of utilities. Tango has some of
those things too. If not already done, I think Andrei Alexandrescu must stop
and work with the Tango team to reduce duplicated efforts :-) The actual
merging of Tango and Phobos can start from a "simple" module like this too
(instead of keeping the silly working in parallel).
- I think most of it can be backported to D 1.0.
- map: flattening successive ranges is a conflation of two different functions,
that is chain and map. It's much better to keep functions logically clean. Perl
shows what problems gives the automatic flattening. When receiveds multiple
iterables map has to map a multi-way function on them. See my d libs.
- it's useful to create lazy versions of map, filter, etc, I have called them
xmap, xfilter, etc.
- Instead of defining map, filter, etc, I think a Python list comphrension is
better, cleaner, simpler to read, etc.
- In my d libs everywere I give an AA, the functions iterate on their *keys*.
This is much more useful, because given a key you can find its value, while
generally the latter is too much slow.
- When the "length" attribute of the input iterable exists, it's used to
pre-allocate the size of the final result in some functions like map().
- inPlace(): in other languages it's called map!(), so it may be called inMap,
or mapBang, etc.
- overwriteAdjacent: I think "compact" may be fitting name (the similar string
function can be removed).
- iterSwap: I don't understand it.
- "The schwartzSort function might require less temporary data and be faster
than the Perl idiom or the decorate-sort-undecorate idiom present in Python and
Lisp. This is because sorting is done in-place and only minimal extra data (one
array of transformed elements) is created.": This is wrong, Python has the
"key" argument of sort/sorted.
- max/min: nicely done. A max/min of iterables (without the need to use reduce)
is useful too (even with 'key' function, see my d libs).

Bye,
bearophile
Mar 04 2008
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
bearophile:

 - max/min: nicely done. A max/min of iterables (without the need to use
reduce) is useful too (even with 'key' function, see my d libs).


Nevermind, I'll not use them, and I'll keep using my max/min functions. This
prints 10:

void main() {
    int a = -10;
    uint b = 10;
    writefln( min(a, b) );
}

The result type here must be a long, it's the only one that gives the right
result whenever a,b of type int,uint.

Related problem: my abs() functions are like this (and I don't like them much
still), they aren't templated:

int abs(int n) {
    assert(n != int.min, "abs(int.min) == int.min");
    return (n >= 0) ? n : -n;
}

Such bug catching show why I think multi-precision integers are useful for far
more than just cryptography: they help avoid many bugs.

Bye,
bearophile
Mar 04 2008
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Bill Baxter:

 Now you've lost me.  You're telling Andrei he should write a library 
 using features that don't exist in D?


You are right, that post of mine was a mixed bag. That comment wasn't for
Andrei, it was just a note: I think that a list comp can avoid you to create
map/filter/xmap/xfilter, and you can improve code readability, etc. So it was
mostly a note for the D developers :-)
Sometimes you look at the language, and you see something that's better if
moved into a standard library (complex numbers?), and other times you look at
the standard library and you see things that are better removed from the std
lib (Python list comprehensions). Similar things happen to the std lib modules,
they can be removed or added according to their usage, etc. becoming third-part
modules, or official std lib modules.They are dynamic equilibriums.

Bye,
bearophile
Mar 05 2008
parent reply Jarrod <qwerty ytre.wq> writes:
On Wed, 05 Mar 2008 11:35:47 -0500, bearophile wrote:


 I think that a list comp can avoid you
 to create map/filter/xmap/xfilter, and you can improve code readability,
 etc.


I disagree. D is a straightforward language. Adding python list 
generation adds a big 'special case' scenario. Wrapping a for loop inside 
square brackets? Hmm I don't think that's better than using map/filter. 
Look at it from a non-python perspective: Every 'for' iteration does not 
generate a return value, so how can each cycle of a for loop logically 
create a list element?
At least with map/filter you can see the cascading pattern straight away. 
By looking at the documentation you know what they return and by being 
seen as functions rather than built in methods, any programmer can see 
how they will flow (simply take arguments in the brackets, spit out a 
return value).

With that said, more ordinary list operations would indeed be a blessing, 
such as:

a,b = 1,2;
a,b = b,a;
return (a,b);


Just my thoughts.
Mar 05 2008
next sibling parent reply =?ISO-8859-1?Q?Jari-Matti_M=E4kel=E4?= <jmjmak utu.fi.invalid> writes:
On Thu, 6 Mar 2008, Jarrod wrote:


 On Wed, 05 Mar 2008 11:35:47 -0500, bearophile wrote:


 I think that a list comp can avoid you
 to create map/filter/xmap/xfilter, and you can improve code readability,
 etc.


 I disagree. D is a straightforward language. Adding python list
 generation adds a big 'special case' scenario. Wrapping a for loop inside
 square brackets? Hmm I don't think that's better than using map/filter.
 Look at it from a non-python perspective: Every 'for' iteration does not
 generate a return value, so how can each cycle of a for loop logically
 create a list element?
 At least with map/filter you can see the cascading pattern straight away.
 By looking at the documentation you know what they return and by being
 seen as functions rather than built in methods, any programmer can see
 how they will flow (simply take arguments in the brackets, spit out a
 return value).


One advantage of list/array comprehensions is that the language can more 
easily optimize the "query" (I guess LINQ like stuff is becoming more 
common these days). With subsequent function calls the compiler would need 
fairly advanced syntax tree manipulation strategies that may be hard to 
reason about unless the functions are pure. I won't say anything about the 
declarative nature since the syntax, if fitted to D, would not probably 
be very cute anyway.


 With that said, more ordinary list operations would indeed be a blessing,
 such as:

 a,b = 1,2;
 a,b = b,a;
 return (a,b);




List operations? These look like first class tuples to me. Let's hope they 
are still on the todo list.


 Just my thoughts.
Mar 06 2008
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Jari-Matti Mäkelä:

I won't say anything about the declarative nature since the syntax, if fitted
to D, would not probably be very cute anyway.<


I think a LINQ-like syntax may be enough, if a Python/Haskell syntax doesn't
fit well in the language.

Bye,
bearophile
Mar 06 2008
prev sibling parent Jarrod <qwerty ytre.wq> writes:
On Thu, 06 Mar 2008 13:28:11 +0200, Jari-Matti Mäkelä wrote:


 List operations? These look like first class tuples to me. Let's hope
 they are still on the todo list.


Semantics, my arch nemesis. We meet again.
Mar 07 2008
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Jarrod:

 I disagree. D is a straightforward language. Adding python list 
 generation adds a big 'special case' scenario. Wrapping a for loop inside 
 square brackets? Hmm I don't think that's better than using map/filter. 


For more of your amusement, the following is a little Python program coming
from here:
http://wordaligned.org/articles/why-python-programmers-should-learn-python
That refers to the last pages of this document:
http://www.keithbraithwaite.demon.co.uk/professional/presentations/2003/ot/why_learn_python.pdf

My Python version:

def inverter(n):
    n2txt = "zero one two three four five six seven eight nine".split()
    txt2n = dict((digit, str(i)) for i, digit in enumerate(n2txt))
    if isinstance(n, basestring):
        return int("".join(txt2n[p] for p in n.split()))
    else:
        return " ".join(n2txt[int(d)] for d in str(n))





My (working) D translation (with my d libs):

import std.string, d.func, std.conv, d.string;

template Inverse(T) {
    static if(IsType!(T, byte, ubyte, int, uint, long, ulong))
        alias string Inverse;
    else
        alias long Inverse;
}

Inverse!(T) inverter(T)(T n) {
    auto n2txt = "zero one two three four five six seven eight nine".split();
    auto txt2n = dict(zip(n2txt, map(&format, xrange(10)) ));
    static if(IsType!(T, byte, ubyte, int, uint, long, ulong))
        return map((char d){return n2txt[toInt(d~"")];}, str(n)).join(' ');
    else
        return toInt(map((string p){return str(txt2n[p]);},
n.split()).joinArr());

}

void main() {
    putr(inverter(752));
    putr(inverter("seven five two"));
}

As you can see the D version uses map() and various anonymous functions that
clutter code making it not much readable, despite those many helpers. In the
end I am probably not going to use such D code, while in Python that code
despite being a bit slow is almost acceptable.

Bye,
bearophile
Mar 06 2008
parent Jarrod <qwerty ytre.wq> writes:
Perhaps I wasn't too clear about what I meant. I recall you saying D 
should have python list comps, and anything else is not worth it. I 
wasn't saying D should go without any list generation at all, I just 
think the python method of going about it may not exactly 'gel' well with 
a language like D. The first alternative that comes to mind for me, is 
map. Clearly there are other methods to go about it, but map and filter 
are already in std2.


Oh and I couldn't help myself, I had to throw together this quick perl 
version of your program:

 sub inverse{
 	my  n2txt = qw(zero one two three four five six seven eight nine);
 	my $c;
 	my %txt2n = map {($_,$c++)}  n2txt;
 
 	my $n = shift;
 	if ($n =~ /^\d+$/){
 		return join ' ', map {$n2txt[$_]} split '', $n;
 	} 
 	else{
 		return join '', map {$txt2n{$_}} split ' ', $n;
 	}
 }
 print inverse(inverse(752))."\n";


Makes you wonder if python style list comps in D would end up any better 
than map did.
Mar 07 2008