On Sun, Oct 07, 2007 at 10:51:23PM +0100, Janice Caron wrote:
>On 10/6/07, Bill Baxter <dnewsgroup@billbaxter.com> wrote:
>> Here's a 10min prototype:
>> <snip>
>
>>      writefln( accum!("+",int)([1,2,3,4,5]) );
>>      writefln( accum!("*",int)([1,2,3,4,5]) );
>
>Granted that was a ten minute prototype, but please allow me to point
>out that it falls down with zero-element arrays.
>
>int[] a;
>accum!("+",int)(a) // should evaluate to 0
>accum!("*",int)(a) // should evaluate to 1
>
>I'd still vote no to the original idea though, because the language
>can already do what is required. As many others have pointed out, it
>would be easy to write functions like sum() and product() - and to
>templatise them for any type, and to be honest, something like

This operation (usually called 'fold') is very useful in a functional-style
of programming.  Although this can be done, to some extent, in D, it
probably isn't all that common.  Haskell provides numerous fold operations
on whether the operator is applied from the left or the right, and how the
zero term is handled (in fact, it provides an entire module of utilities,
along with a "Class", which is kind of like an interface, for things that
are foldable).

For the zero term, you can either provide what the zero element is, or
disallow the zero element case.

But, I agree, this doesn't need to be in the language, since it is easy to
write.

Dave

On 10/7/07, David Brown <dlang@davidb.org> wrote:
> But, I agree, this doesn't need to be in the language, since it is easy to write.

It is worth pondering about efficiency though. Most especially when it comes to concatenation. That is:

string s = cat(a,b,c,d,e,f,g,h);

ought to be more efficient than

string s = a~b~c~d~e~f~g~h;

because the former could, in principle, require only one allocation, wheras the latter needs seven.

The fast way:
s.length = a.length + b.length + ...
s[0..a.length] = a[];
s[a.length..a.length+b.length] = b[];
...

Order O(N)

The slow way:
s = a ~ b;
s = s ~ c;
...
s = s ~ h;

Order O(N squared)

>> will u use these templates? why not?
> 
> I probably wouldn't use the functionality much at all, no matter what syntax it's wrapped up in.

me too :-) (i don't even like my syntax ideas)

> Here's something you might like to read.
> http://www.artima.com/weblogs/viewpost.jsp?thread=98196

> As Guido puts it, aside from those few examples I gave above, there's really not that much use for that functionality.  And when it is needed for something other than those things it's often more readable to just write out the foreach.

ok maybe the array operation stuff is too special for a general in-language solution - thx

> It is worth pondering about efficiency though. Most especially when it
> comes to concatenation. That is:
> 
> string s = cat(a,b,c,d,e,f,g,h);
> 
> ought to be more efficient than
> 
> string s = a~b~c~d~e~f~g~h;
> 
> because the former could, in principle, require only one allocation,
> wheras the latter needs seven.

only if the compiler don't understand whats going on
who says that a compiler need to seperate each concatenate in a single operation? its the compilers job to use an efficent way

do you think that a array slice works the same?

int b[5] = [1,2,3,4,5]
int t[3] = b[1..3]

t[0] = &b[1]
t[1] = &b[2]

btw: i understand that my idea just adress 2% of the array operations needs - so i rejeced it myself (clean brain again)

ciao dennis

On 10/8/07, dennis luehring <dl.soluz@gmx.net> wrote:
> only if the compiler don't understand whats going on
> who says that a compiler need to seperate each concatenate in a single
> operation? its the compilers job to use an efficent way

That's a very interesting question. I have absolutely no idea what the answer is. Will the compiler optimize a~b~c~d~e~f~g~h into a single allocation and some copying? I don't know. I hope so, but I suspect not.

The existence of a cat() function would certainly encourage people to write code in a concatenation-optimal way though.

(Note: I am /not/ suggesting that such a feature be added to D, because the function is just too easy to write).



> do you think that a array slice works the same?

Of course not. Slicing doesn't involve /any/ allocations!

Janice Caron wrote:
> On 10/7/07, David Brown <dlang@davidb.org> wrote:
>> But, I agree, this doesn't need to be in the language, since it is easy to
>> write.
> 
> It is worth pondering about efficiency though. Most especially when it
> comes to concatenation. That is:
> 
> string s = cat(a,b,c,d,e,f,g,h);
> 
> ought to be more efficient than
> 
> string s = a~b~c~d~e~f~g~h;
> 
> because the former could, in principle, require only one allocation,
> wheras the latter needs seven.
> 
> The fast way:
> s.length = a.length + b.length + ...
> s[0..a.length] = a[];
> s[a.length..a.length+b.length] = b[];
> ...
> 
> Order O(N)

Actually, DMD optimizes the second case by calling a special function in the runtime library for concatenating >2 arrays. It works in your "fast way".

For some reason GDC (0.24) seems to also call that function (even in the 2-array case) but with only two arrays at a time, defeating the purpose :(.
(I only found out about this bug while writing this post, and filed a report: http://d.puremagic.com/issues/show_bug.cgi?id=1556)

Janice Caron wrote:
> On 10/8/07, dennis luehring <dl.soluz@gmx.net> wrote:
>> only if the compiler don't understand whats going on
>> who says that a compiler need to seperate each concatenate in a single
>> operation? its the compilers job to use an efficent way
> 
> That's a very interesting question. I have absolutely no idea what the
> answer is. Will the compiler optimize a~b~c~d~e~f~g~h into a single
> allocation and some copying? I don't know. I hope so, but I suspect
> not.

As I wrote in my previous post (which I started before my seeing this post of yours) DMD will optimize into a single alloc, but GDC won't.
I've filed a bug[1] for the latter, since the multi-concat function is available in gphobos and is even called by the generated code but only for two arrays at a time (thus defeating the purpose).


[1]: http://d.puremagic.com/issues/show_bug.cgi?id=1556

> The existence of a cat() function would certainly encourage people to
> write code in a concatenation-optimal way though.
> 
> (Note: I am /not/ suggesting that such a feature be added to D,
> because the function is just too easy to write).

The optimization should be pretty easy for the compiler (and is in fact performed by DMD, even without -O), and just using concats looks cleaner IMHO.

On 10/8/07, Frits van Bommel <fvbommel@remwovexcapss.nl> wrote:
> DMD will optimize into a single alloc

Great! Except...

How does that work for opCat() and opCatAssign()? Can those functions accept multiple inputs? One would certainly hope so, given what you've explained, but I've not seen it documented anywhere. It would be a shame if user-created collections couldn't benefit from that optimization.