January 15, 2013
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
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
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
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
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
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
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
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
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
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.