Improving std.algorithm.find

[Philippe Sigaud]

On Mon, Jul 19, 2010 at 21:23, Andrei Alexandrescu <
SeeWebsiteForEmail at erdani.org> wrote:

>
> What I personally would like is a way to find an element in an ordered
>> container (binary tree...)
>>
>
> Wouldn't that be a member of the binary tree?
>

Yes, indeed. Unless I define some cousin to range, a recursive range, to
iterate on any recursive container, like trees or graphs and then devise
algorithms on them. I played with this idea a few weeks ago but went to do
other things. Anyway, carry on.
Btw, I still plan to update some simple generic graphs and trees structs to
obey TotalContainer interface when it makes sense, and update my graph
algorithms accordingly. If I ever get somewhere, I'll post something.



>
>     Aren't such scenarios better served by putting the limits inside the
>>    predicate? Otherwise the list of what can be done could go on forever.
>>
>>
>> The problem is that, as the predicate is passed at compile-time, the
>> limits must be CT-defined too. I'd like the limits to be defined at
>> runtime. I run into this regularly, while using predicates in
>> std.algorithms.
>>
>
> I think this is a misunderstanding. All of std.algorithm works with
> delegates:
>
>
>    int[] a = [ 1, 4, 2, 3 ];
>    int b = 2;
>    assert(find!((x) { return x > b; })(a) == [4, 2, 3]);
>
> Ah yes, but I regularly use algorithms structs as return values, like this:

auto nTimes(E, R)(E multiplier, R range)
{
    return map!((ElementType!R e) { return e*multiplier;})(range);
}

Error: delegate std.algorithm.__dgliteral2 cannot access frame of function
__dgliteral2|

I ran into this yesterday while trying to encode power series as (possibly
infinite) ranges, and getting problems for the operators overloading. Too
bad, I got to the point where I could calculate sin/cos/exp values quite
precisely and then could easily define derivation and such. There are
workaround, but they are not as handy.
I had the same problems some time ago, trying to define predicates on the
fly, though I cannot right now remember what it was.

I know it's not a problem in std.algorithm per se, but it's a limit on its
usefulness, as far as I'm concerned.



>  Anything that can mimic regex functions on generic ranges is good, IMO.
>> I regularly find myself wanting to do some regex-like matching. We do
>> not need real pattern matching but even with simplified predicates, we
>> can do many things.
>>
>
> I agree we're in desperate need for a good range-based, character-divorced,
> statically-computed regex engine.


Oh, a full statically computed engine would be the Graal. But I did not go
that far. Being able to simply match, split and replace at runtime on any
range would be good also, without going all regex. Heck, I may even have
already coded something like this, I'll go and check.

What I'm trying to do right now as a back-burner task is a function
transforming a range in a set-like range (each element is present only
once), but testing for "did I already see that?" with a user-provided
predicate.


>  I'm sorry I didn't look at your implementation, as I don't know
>> Boyer-Moore that much. Does it need to know the alphabet size or do you
>> use another variant?
>>
>
> My explanation of B-M would do little more than pasting information from
> various places on the Net.
>

OK.


Philippe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20100719/da3594c8/attachment.html>