D2's std.algorithm

Bill Baxter dnewsgroup at billbaxter.com
Tue Dec 18 16:13:20 PST 2007


Sean Kelly wrote:
> Bill Baxter wrote:
>>  >   sort!("a > b")(array);
>>
>> I just wanted to say that this is BRILLIANT!  Zero call overhead, zero 
>> syntax overhead, compile-time lambda functions!
>>
>> All the algorithms should support this syntax so we can do sexy 
>> compile-time lambda one-liners like:
>>
>>    find!("a.some_member > 10")(array);
>>
>> or
>>
>>    partition!("a.call_something() !is null")(array);
>>
>> etc.
> 
> This is a pretty neat trick that has the benefit of providing a succinct 
> syntax that works for both runtime and for CTFE.  However, the overall 
> utility of the approach seems less than is offered by more traditional 
> means.  Complex comparisons could render the function call largely 
> unreadable by requiring a multi-line string to be passed as a template 
> argument, and there is also no means of supplying a comparator at 
> run-time using this method.  For comparison, consider this find routine:
> 
>     template find( Elem, Pred = IsEqual!(Elem) )
>     {
>         size_t find( Elem[] buf, Elem pat, Pred pred = Pred.init )
>         {
>             for( size_t pos = 0; pos < buf.length; ++pos )
>             {
>                 if( pred( buf[pos], pat ) )
>                     return pos;
>             }
>             return buf.length;
>         }
>     }
> 
> With this support comparator:
> 
>     struct IsEqual( T )
>     {
>         static bool opCall( T p1, T p2 )
>         {
>             static if( is( T == class ) || is( T == struct ) )
>                 return (p1 == p2) != 0; // opEquals returns an int
>             else
>                 return p1 == p2;
>         }
>     }
> 
> Because the function used for comparison is static, this code complies 
> and works perfectly with CTFE.  At the same time, the predicate may also 
> be a more complex struct, anonymous delegate, function pointer, named 
> delegate, and so on.  With this in mind, I would be inclined to do 
> something like this to add string predicate support to existing routines:
> 
>     template find( char[] oper )
>     {
>         size_t find(Elem)( Elem[] buf, Elem pat )
>         {
>             return .find!(Elem, Encode!(Elem, oper))( buf, pat );
>         }
>     }
> 
>     struct Encode( T, char[] exp )
>     {
>         static bool opCall( T a, T b )
>         {
>             return mixin(exp);
>         }
>     }
> 
> Thus allowing:
> 
>     const posA = find( "abcdefg", 'c' );            // uses IsEqual
>     const posB = find!("a == b")( "abcdefg", 'c' ); // uses Encode
> 
>     void main()
>     {
>         // uses anonymous delegate at run-time
>         auto posC = find( "abcdefg",
>                           'c',
>                           (char a, char b){ return a == b; } );
>     }
> 
> So I guess what I'm saying is that the string version is a cool idea to 
> be used in addition to the classic approach, but I see little utility in 
> having it replace the classic approach.  And it's easy enough to add the 
> string encoding as a facade over existing functions that nearly anything 
> that accepts a predicate can use the string approach for free.

D2 std.algorithm.sort actually does come in two flavors, the string kind 
and an alias kind.

And in fact the string kind just creates a function that's passed to the 
alias kind.  So it probably doesn't actually eliminate the call overhead 
despite the comparison function being available at compile time.  I was 
a little surprised when I saw that implementation, actually.

Anyway, I just like the idea of using a string literal for comparisons 
for the simple cases.  I tried to use boost::functional once and was 
totally incapable of writing something as trivial as an expression that 
used .member of the argument thingy rather than the argument itself. 
But the string expression makes it completely obvious how to do that. 
And it *should* be inline-able and CTFE-able if you write your templates 
carefully, even if the current implementation is not*.

--bb

* Note that I'm not sure if the std.algorithm implementation is 
CTFE-able or not.  Haven't tried it.  Doesn't look like it would be 
though. Not by DMD at least.



More information about the Digitalmars-d mailing list