www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Range golf challenge: apply predicate to a subrange, returning the

reply FeepingCreature <feepingcreature gmail.com> writes:
AKA "Do My Job For Me Challenge"

You have a range. You have an expression that's a chain of 
`std.algorithm` functions, ie. `filter`, `find`, `until`, `drop`, 
etc. that select a subset of the range. Let's abbreviate it with 
`.select`.

The subset has the same order of elements as the original range. 
The only change is that some elements of the original range will 
be missing.

The elements of the range are not mutable, so you cannot mutate 
the range via `foreach (ref)`. Instead, you have a predicate, 
let's say `.modify`, that takes a value of the range and returns 
a new value.

Task: Given a range `range`, return a new range that consists of 
the elements of `range`, except modified with the `modify` 
predicate at all elements that are part of the subrange selected 
by `.select`.

While ` nogc`.

Note: You are allowed to redefine the types of range elements, as 
long as `select` can see the original value, for instance with 
`value`.

Sketch of a solution: I've been thinking something like 
"`enumerate` the range, apply selector, "left join zip" (zip 
where the enumeration matches, to be written) with the original 
range, apply predicate where left join zip has a match. I'm 
thinking a syntax like 
`range.selectSubrange!select.modifySubrange!modify`.

Thoughts?
Oct 07 2022
next sibling parent reply Andrey Zherikov <andrey.zherikov gmail.com> writes:
On Friday, 7 October 2022 at 14:00:57 UTC, FeepingCreature wrote:

 Task: Given a range `range`, return a new range that consists 
 of the elements of `range`, except modified with the `modify` 
 predicate at all elements that are part of the subrange 
 selected by `.select`.


May be I misunderstood but why doesn't `.select.map` work here?
Oct 07 2022
parent reply FeepingCreature <feepingcreature gmail.com> writes:
On Friday, 7 October 2022 at 14:16:19 UTC, Andrey Zherikov wrote:

 On Friday, 7 October 2022 at 14:00:57 UTC, FeepingCreature 
 wrote:

 Task: Given a range `range`, return a new range that consists 
 of the elements of `range`, except modified with the `modify` 
 predicate at all elements that are part of the subrange 
 selected by `.select`.


 May be I misunderstood but why doesn't `.select.map` work here?


`range.select` returns a subrange of `range`. What's desired is 
"`range`, but with the *subrange only* mapped to `modify`."
Oct 07 2022
parent reply FeepingCreature <feepingcreature gmail.com> writes:
On Friday, 7 October 2022 at 15:18:08 UTC, FeepingCreature wrote:

 `range.select` returns a subrange of `range`. What's desired is 
 "`range`, but with the *subrange only* mapped to `modify`."


For example!

```
auto result = 10.iota.selectSubrange!isEven.mapSubrange!"a * 2";

assert(result.equal([0, 1, 4, 3, 8, 5, 12, 7, 16, 9]));
```
Oct 07 2022
parent reply Andrey Zherikov <andrey.zherikov gmail.com> writes:
On Friday, 7 October 2022 at 15:20:50 UTC, FeepingCreature wrote:

 On Friday, 7 October 2022 at 15:18:08 UTC, FeepingCreature 
 wrote:

 `range.select` returns a subrange of `range`. What's desired 
 is "`range`, but with the *subrange only* mapped to `modify`."


 For example!

 ```
 auto result = 10.iota.selectSubrange!isEven.mapSubrange!"a * 2";

 assert(result.equal([0, 1, 4, 3, 8, 5, 12, 7, 16, 9]));
 ```


```d
10.iota.map!(_ => _.isEven ? _*2 : _); // => [0, 1, 4, 3, 8, 5, 
12, 7, 16, 9]
```
Oct 07 2022
parent reply Andrey Zherikov <andrey.zherikov gmail.com> writes:
On Friday, 7 October 2022 at 16:32:07 UTC, Andrey Zherikov wrote:

 ```d
 10.iota.map!(_ => _.isEven ? _*2 : _); // => [0, 1, 4, 3, 8, 5, 
 12, 7, 16, 9]
 ```


You can even generalize this:
```d
alias mapSubrange(alias filter, alias transform) = map!(_ => 
filter(_) ? transform(_) : _);
10.iota.mapSubrange!(isEven, _ => _*2);
```
Oct 07 2022
parent =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 10/7/22 09:35, Andrey Zherikov wrote:

 On Friday, 7 October 2022 at 16:32:07 UTC, Andrey Zherikov wrote:

 ```d
 10.iota.map!(_ => _.isEven ? _*2 : _); // => [0, 1, 4, 3, 8, 5, 12, 7,
 16, 9]
 ```


 You can even generalize this:
 ```d
 alias mapSubrange(alias filter, alias transform) = map!(_ => filter(_) ?
 transform(_) : _);
 10.iota.mapSubrange!(isEven, _ => _*2);
 ```


I was trying something similar where I left .map to the user code:

import std;

bool isEven(T)(T value) {
     return !(value % 2);
}

alias applyIf(alias pred, alias func) = value => (pred(value) ? 
func(value) : value);

void main() {
     auto result = 10.iota.map!(applyIf!(isEven, a => a * 2));
     assert(result.equal([0, 1, 4, 3, 8, 5, 12, 7, 16, 9]));
}

Ali
Oct 07 2022
prev sibling next sibling parent reply rassoc <rassoc posteo.de> writes:
On 10/7/22 16:00, FeepingCreature via Digitalmars-d wrote:

 Thoughts?


How about your selector func wraps the elements, similar to Nullable or via
SumType, and your modifier func operates on the marked ones during iteration
while returning the others as is? Poor man's monads?
Oct 07 2022
parent reply FeepingCreature <feepingcreature gmail.com> writes:
On Friday, 7 October 2022 at 16:49:33 UTC, rassoc wrote:

 On 10/7/22 16:00, FeepingCreature via Digitalmars-d wrote:

 Thoughts?


 How about your selector func wraps the elements, similar to 
 Nullable or via SumType, and your modifier func operates on the 
 marked ones during iteration while returning the others as is? 
 Poor man's monads?


Y'all are missing the point a bit. :)

The type spec of the selector is "takes a range, returns a 
subrange." A subrange here being "a range like the original but 
with some amount of elements missing." Not, specifically, a 
predicate! That's what makes it interesting! :)
Oct 07 2022
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 10/7/22 12:19, FeepingCreature wrote:

 On Friday, 7 October 2022 at 16:49:33 UTC, rassoc wrote:

 On 10/7/22 16:00, FeepingCreature via Digitalmars-d wrote:

 Thoughts?


 How about your selector func wraps the elements, similar to Nullable
 or via SumType, and your modifier func operates on the marked ones
 during iteration while returning the others as is? Poor man's monads?


 Y'all are missing the point a bit. :)


It's because of your example! :)


 The type spec of the selector is "takes a range, returns a subrange." A
 subrange here being "a range like the original but with some amount of
 elements missing."


Your example does not miss the "missing" elements (the odd ones):

   assert(result.equal([0, 1, 4, 3, 8, 5, 12, 7, 16, 9]));

Maybe you mean selectSubrange is already written and does miss some 
elements and the goal is to merge those back into where they were 
missing from.

Ali
Oct 07 2022
parent reply FeepingCreature <feepingcreature gmail.com> writes:
On Friday, 7 October 2022 at 20:19:07 UTC, Ali Çehreli wrote:

 On 10/7/22 12:19, FeepingCreature wrote:

 On Friday, 7 October 2022 at 16:49:33 UTC, rassoc wrote:

 On 10/7/22 16:00, FeepingCreature via Digitalmars-d wrote:

 Thoughts?


 How about your selector func wraps the elements, similar to




 Nullable

 or via SumType, and your modifier func operates on the




 marked ones

 during iteration while returning the others as is? Poor




 man's monads?

 Y'all are missing the point a bit. :)


 It's because of your example! :)


 The type spec of the selector is "takes a range, returns a


 subrange." A

 subrange here being "a range like the original but with some


 amount of

 elements missing."


 Your example does not miss the "missing" elements (the odd 
 ones):


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."


   assert(result.equal([0, 1, 4, 3, 8, 5, 12, 7, 16, 9]));

 Maybe you mean selectSubrange is already written and does miss 
 some elements and the goal is to merge those back into where 
 they were missing from.

 Ali


Yes, exactly.
Oct 08 2022
next sibling parent "H. S. Teoh" <hsteoh qfbox.info> writes:
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
Oct 08 2022
prev sibling parent "H. S. Teoh" <hsteoh qfbox.info> writes:
On Sat, Oct 08, 2022 at 12:45:29PM -0700, H. S. Teoh via Digitalmars-d wrote:
[...]

 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).


Merge, i.e., with std.algorithm.multiwayMerge.



 - 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.


[...]


T

-- 
Do not reason with the unreasonable; you lose by definition.
Oct 08 2022
prev sibling parent "H. S. Teoh" <hsteoh qfbox.info> writes:
On Fri, Oct 07, 2022 at 04:49:33PM +0000, rassoc via Digitalmars-d wrote:

 On 10/7/22 16:00, FeepingCreature via Digitalmars-d wrote:

 Thoughts?


 
 How about your selector func wraps the elements, similar to Nullable
 or via SumType, and your modifier func operates on the marked ones
 during iteration while returning the others as is? Poor man's monads?


Another way is if you convert .select into a predicate, then:

	auto r = myrange.map!(e => pred(e) ? modify(e) : e);

But that depends on how easy it is to convert .select into a predicate.


T

-- 
If lightning were to ever strike an orchestra, it'd always hit the conductor
first.
Oct 07 2022