Range golf challenge: apply predicate to a subrange, returning the original range modified.

[H. S. Teoh]

On Sat, Oct 08, 2022 at 05:08:17PM +0000, FeepingCreature via Digitalmars-d wrote:
[...]
> Right: the *selector* here is `filter!isEven`, which produces a range
> of `0, 2, 4, 6, 8` or variations thereof. The point is to get a range
> where every element that `filter!isEven` selected has been modified by
> `square`, while *keeping* the unselected elements in the same order.
> 
> And that's fairly straightforward for `filter!isEven` because `isEven`
> is a predicate. But, for instance, `find` or `until` aren't
> predicates. So in a way, the question is "how do you predicatize an
> arbitrary subrange selection expression."

It's actually not that hard, you just have to use std.range.indexed to
tag the selected range, then merge the original with the modified range.

Here's a sketch of my idea:
- Pair the range with an index using .indexed, pass that through .select
  to get the filtered range.
   - Use .map to map it to the modified elements.
   - Furthermore, tag each element with a secondary index of 0
     (explained below).
- Pair the original range with .indexed, plus a secondary index of 1.
- Merge the two ranges together so that the result is lexicographically
  sorted according the indexing order (i.e., filtered elements will
  appear in the right positions in the original range) and the secondary
  index (i.e., replaced elements appear first in the resulting range).
- Pass the merged range to .uniq to replace the filtered values with
  their modified counterparts, with uniqueness predicate defined by the
  (first) index. This effectively drops elements whose secondary index
  is 1 if they have a replacement, otherwise they are left untouched.
- Unwrap the elements to drop the indices to obtain the final result.

//

Proof-of-concept example:

origRange: A B C D E F G H
origRange.select: B F G
Replacement values for .select: X Y Z

origRange indexed, plus secondary index of 1:
	(0,1,A) (1,1,B) (2,1,C) (3,1,D) (4,1,E) (5,1,F) (6,1,G) (7,1,H)

Selected range indexed, plus secondary index of 2:
	(1,0,B) (5,0,F) (6,0,G)

Selected range with modified values substituted using .map:
	(1,0,X) (5,0,Y) (6,0,Z)

Merge the two ranges in lexicographic order of first two elements:
	(0,1,A) (1,0,X) (1,1,B) (2,1,C) (3,1,D) (4,1,E) (5,0,Y) (5,1,F)
	(6,0,Z) (6,1,G) (7,1,H)

Pass merged range through .uniq, with equivalence defined solely by
first index (first element with a particular index gets picked up,
subsequent elements with the same index are dropped):
	(0,1,A) (1,0,X) (2,1,C) (3,1,D) (4,1,E) (5,0,Y) (6,0,Z) (7,1,H)

Unwrap the range:
	A X C D E Y Z H

QED. ;-)


T

-- 
Javascript is what you use to allow third party programs you don't know anything about and doing you know not what to run on your computer. -- Charles Hixson