View mode: basic / threaded / horizontal-split · Log in · Help
January 15, 2013
Re: The rfind challenge
On Tuesday, 15 January 2013 at 19:44:39 UTC, FG wrote:
> On 2013-01-15 19:00, Andrei Alexandrescu wrote:
>> That's too many. Simpler approaches?
>
>
> Let me give an outside perspective of someone that doesn't work 
> with D all day.
> For forward ranges the original method is fine, but for 
> bidirectional r and e I would expect the following code to 
> somehow just work, but it doesn't:
>
>     auto rfind(R1 r, R2 e) {
>         return retro(findSplitAfter(retro(r), retro(e))[0]);
>     }
>
> Other than the tiny detail of this not working, existing stuff 
> like findSplit, findSplitBefore and findSplitAfter would be 
> enough to define their r* versions.

Well, you just stumbled on the entire problem.

Given a bidirectional range BR, findSplitBefore actually cheats. 
This is the basic algorithm: popFront until you find the what you 
are looking for. Return the found range, as well as "what was 
before"

The problem is that there is no real way to return "what was 
before", so we use a tool called "Take", that adapts a range to 
only hold the first N elements. Basically, it returns "take(br, 
n)". The problem though is that:
a) The type is not BR anymore, but Take!BR
b) Take!BR is not bidirectional.

So basically:
//--------
BR br = BR(1, 2, 3, 4);
result = br.findSplitAfter([3]);
auto lhs = result[0]; //[1, 2]
auto rhs = result[1]; //[4]
//typeof(lhs): Take!BR
//typeof(rhs): BR
//--------

And this is the root problem. As you can see, element 0 is not 
actually a bidirectional range anymore, nor is it of type BR 
either. This "tiny detail" as you say, is actually fundamental ;)

This is why I'd like to find a way to cut bidirectional ranges: 
Not just for r* functions, but also for our everyday functions: 
As you can see, we don't have any way to "findBefore" and store 
the result in a BR. Ouch.

As a user of D, I agree with you that it should "just work". Real 
life is different though :/
January 15, 2013
Re: The rfind challenge
On 2013-01-15 21:14, monarch_dodra wrote:
> This is why I'd like to find a way to cut bidirectional ranges: Not just for r*
> functions, but also for our everyday functions: As you can see, we don't have
> any way to "findBefore" and store the result in a BR. Ouch.
>
> As a user of D, I agree with you that it should "just work". Real life is
> different though :/


Ah, right. That Take has bitten me before when I was discussing string slicing 
using negative indexes. :)

In that case I wish this cutting that preserves the type of range will get 
implemented and the cheats in findSplit removed.
January 15, 2013
Re: The rfind challenge
On 1/15/13 2:07 PM, Phil Lavoie wrote:
> Continuing with reversible ranges:

I don't think .reverse will take us far enough. Won't work with arrays 
which kinda puts a monkey wrench into everything. r1.before(r2) works 
much better:

R rfind(R, E)(R r, E e) {
  auto original = r.save;
  for (; !r.empty; r.popBack) {
    if (r.endsWith(e)) break;
  }
  return original.before(r);
}

The generic implementation of before is trivial:

auto before(R)(R theBuck, R stopsHere) {
  static struct Result {
    bool empty() { return r1 is r2; }
    auto ref front() { return r1.front; }
    void popFront() { r1.popFront; }
    private R r1, r2;
  }
  return Result(theBuck, stopsHere);
}

For random-access ranges:

auto before(R)(R theBuck, R stopsHere) {
  return theBuck[0 .. theBuck.length - stopsHere.length];
}

(Glossing over checks and balances etc.)

Bidirectional ranges would need to implement before natively to return 
the same type as the original range.

The question is whether before() is enough for many other algorithms 
we'd want to define.


Andrei
January 15, 2013
Re: The rfind challenge
On Tue, Jan 15, 2013 at 03:59:17PM -0500, Andrei Alexandrescu wrote:
> On 1/15/13 2:07 PM, Phil Lavoie wrote:
> >Continuing with reversible ranges:
> 
> I don't think .reverse will take us far enough. Won't work with
> arrays which kinda puts a monkey wrench into everything.
[...]

Not really. We can define an array wrapper with a .reverse that returns
the original array, something like:

	// In std.array
	auto reverse(R)(R array)
		if (is(R _ : E[], E)
	{
		static struct ReverseArray {
			R[] src;

			@property auto front() { return src[$-1]; }
			@property bool empty() { return src.empty; }
			@property void popFront() {
				src = src[0..$-1];
			}
			@property auto reverse() {
				return src;
			}
			... // other wrapper methods
		}
		return ReverseArray(array);
	}

This will let you implement rfind in a way that returns the original
array.


T

-- 
Not all rumours are as misleading as this one.
January 15, 2013
Re: The rfind challenge
On 1/15/13 4:22 PM, H. S. Teoh wrote:
> On Tue, Jan 15, 2013 at 03:59:17PM -0500, Andrei Alexandrescu wrote:
>> On 1/15/13 2:07 PM, Phil Lavoie wrote:
>>> Continuing with reversible ranges:
>>
>> I don't think .reverse will take us far enough. Won't work with
>> arrays which kinda puts a monkey wrench into everything.
> [...]
>
> Not really. We can define an array wrapper with a .reverse that returns
> the original array

Yah, there's retro already. My point is .reverse is not powerful enough. 
From what I can tell .before is.

Andrei
January 15, 2013
Re: The rfind challenge
On Tuesday, 15 January 2013 at 21:24:19 UTC, H. S. Teoh wrote:
> On Tue, Jan 15, 2013 at 03:59:17PM -0500, Andrei Alexandrescu 
> wrote:
>> On 1/15/13 2:07 PM, Phil Lavoie wrote:
>> >Continuing with reversible ranges:
>> 
>> I don't think .reverse will take us far enough. Won't work with
>> arrays which kinda puts a monkey wrench into everything.
> [...]
>
> Not really. We can define an array wrapper with a .reverse that 
> returns
> the original array, something like:
>
> 	// In std.array
> 	auto reverse(R)(R array)
> 		if (is(R _ : E[], E)
> 	{
> 		static struct ReverseArray {
> 			R[] src;
>
> 			@property auto front() { return src[$-1]; }
> 			@property bool empty() { return src.empty; }
> 			@property void popFront() {
> 				src = src[0..$-1];
> 			}
> 			@property auto reverse() {
> 				return src;
> 			}
> 			... // other wrapper methods
> 		}
> 		return ReverseArray(array);
> 	}
>
> This will let you implement rfind in a way that returns the 
> original
> array.
>
>
> T

I'm having trouble understanding what you guys are going on 
about. Isn't this "reverse" just retro? And how would it solve 
anything, when retro doesn't?

I thought the point of "reverse" was that it preserved type, but 
this adapter doesn't do that...

Sorry for being dense, but I don't get it :/ I may have missed 
something earlier in the thread. Could you elaborate on the 
solution...?
January 15, 2013
Re: The rfind challenge
On Tuesday, 15 January 2013 at 20:59:17 UTC, Andrei Alexandrescu 
wrote:
> On 1/15/13 2:07 PM, Phil Lavoie wrote:
>> Continuing with reversible ranges:
>
> I don't think .reverse will take us far enough. Won't work with 
> arrays which kinda puts a monkey wrench into everything. 
> r1.before(r2) works much better:
>
> R rfind(R, E)(R r, E e) {
>   auto original = r.save;
>   for (; !r.empty; r.popBack) {
>     if (r.endsWith(e)) break;
>   }
>   return original.before(r);
> }
>
> The generic implementation of before is trivial:
>
> auto before(R)(R theBuck, R stopsHere) {
>   static struct Result {
>     bool empty() { return r1 is r2; }
>     auto ref front() { return r1.front; }
>     void popFront() { r1.popFront; }
>     private R r1, r2;
>   }
>   return Result(theBuck, stopsHere);
> }
>
> For random-access ranges:
>
> auto before(R)(R theBuck, R stopsHere) {
>   return theBuck[0 .. theBuck.length - stopsHere.length];
> }
>
> (Glossing over checks and balances etc.)
>
> Bidirectional ranges would need to implement before natively to 
> return the same type as the original range.
>
> The question is whether before() is enough for many other 
> algorithms we'd want to define.
>
>
> Andrei

But the goal was having a range that start at needle, and ends at 
haystackEnd. Your implementation doesn't do that. It would have 
to use a "after" instead of a "before".

Your "before" proposal is similar to a take, but instead of being 
"index" based, it is "sentinel" based. This does have its 
strengths too, but doesn't solve the problem.

The problem is that "after", just like the would be "takeBack", 
can't offer the front primitive for bidirectional ranges.

I think that long story short, and regardless of return types:
Unless the range has some sort of built-in primitive that allows 
some form of extracting a subrange from it, there is no way to 
obtain a range from the back of a bidirectional range.
January 15, 2013
Re: The rfind challenge
On 2013-01-15 21:59, Andrei Alexandrescu wrote:
> The generic implementation of before is trivial:
>
> auto before(R)(R theBuck, R stopsHere) {
>    static struct Result {
>      bool empty() { return r1 is r2; }
>      auto ref front() { return r1.front; }
>      void popFront() { r1.popFront; }
>      private R r1, r2;
>    }
>    return Result(theBuck, stopsHere);
> }

I'm scared and would feel safer with:
bool empty() { return r1 is r2 || r1.empty(); }


>
> For random-access ranges:
>
> auto before(R)(R theBuck, R stopsHere) {
>    return theBuck[0 .. theBuck.length - stopsHere.length];
> }

This implies that theBuck._end == stopsHere._end, but why?
January 15, 2013
Re: The rfind challenge
On 1/15/13 4:57 PM, monarch_dodra wrote:
> On Tuesday, 15 January 2013 at 20:59:17 UTC, Andrei Alexandrescu wrote:
[snip]
> But the goal was having a range that start at needle, and ends at
> haystackEnd. Your implementation doesn't do that. It would have to use a
> "after" instead of a "before".

Sorry, got ahead of myself. r.retro.before would be needed, which 
requires r.after. I'd like to only add one primitive if at all possible, 
or have a solid proof that two are needed. Back to the drawing board...

Andrei
January 16, 2013
Re: The rfind challenge
On Tuesday, 15 January 2013 at 12:54:12 UTC, Andrei Alexandrescu 
wrote:
> On 1/15/13 1:31 AM, H. S. Teoh wrote:
>> Hmm. What about introducing a new primitive takeUntil, that 
>> returns the
>> initial segment of the range until a given predicate becomes 
>> true? Then
>> you could implement rfind thus:
>>
>> 	auto rfind(alias pred, R)(R range)
>> 		if (isBidirectionalRange!R)
>> 	{
>> 		return range.retro()
>> 			.takeUntil!pred()
>> 			.retro();
>> 	}
>
> That works, but returns a different type. Ideally rfind would 
> return the same type as the initial range, R.
>
> Andrei

Retro of retro is supposed to give back the original range, so I 
don't think it does.
1 2 3 4 5
Top | Discussion index | About this forum | D home