www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - to compose or hack?

reply Steven Schveighoffer <schveiguy gmail.com> writes:
So I have this situation where I need to split a string, then where the 
splits are, insert a string to go between the elements making a new 
range, all without allocating (hopefully).

Looking around phobos I found inside the documentation of 
[roundRobin](https://dlang.org/phobos/std_range.html#.roundRobin) 
something that does *exactly* what I'm looking for.

Except... the provided `interleave` function iterates the original range 
twice, which means 2x the searching calls for splitter. Why does it do 
this? Because `roundRobin` will keep going as long as ANY range still 
has data left, so you need to make the "interleaving" range stop when 
the first one stops.

After struggling to think up ways to compose this (hm.., can  I make the 
ranges share a stopping point?) without the 2x penalty, I just decided 
to write my own interleave range which does exactly what I am looking for:

```d
auto interleave(R, U)(R src, U middles) if (isInputRange!R && is(U == 
ElementType!R))
{
     static struct Result
     {
         R src;
         U middles;
         bool between = false;
         auto front() {
             assert(!empty);
             return between ? middles : src.front;
         }
         void popFront() {
             assert(!empty);
             if(between)
                 between = false;
             else
             {
                 src.popFront;
                 between = true;
             }
         }
         bool empty()
         {
             return src.empty;
         }
     }

     return Result(src, middles);
}
```

This is pretty minimal, but does what I want it to do. Is it ready for 
inclusion in Phobos? Not by a longshot! A truly generic interleave would 
properly forward everything else that the range supports (like `length`, 
`save`, etc).

But it got me thinking, how often do people roll their own vs. trying to 
compose using existing Phobos nuggets? I found this pretty satisfying, 
even if I didn't test it to death and maybe I use it only in one place. 
Do you find it difficult to use Phobos in a lot of situations to compose 
your specialized ranges?

Oh, and if you do know of a better way to compose the range that doesn't 
require the double iteration, I'd be interested in seeing it.

-Steve
Jul 06 2021
next sibling parent reply Jon Degenhardt <jond noreply.com> writes:
On Wednesday, 7 July 2021 at 01:44:20 UTC, Steven Schveighoffer 
wrote:

 This is pretty minimal, but does what I want it to do. Is it 
 ready for inclusion in Phobos? Not by a longshot! A truly 
 generic interleave would properly forward everything else that 
 the range supports (like `length`, `save`, etc).

 But it got me thinking, how often do people roll their own vs. 
 trying to compose using existing Phobos nuggets? I found this 
 pretty satisfying, even if I didn't test it to death and maybe 
 I use it only in one place. Do you find it difficult to use 
 Phobos in a lot of situations to compose your specialized 
 ranges?


I try to compose using existing Phobos facilities, but don't 
hesitate to write my own ranges. The reasons are usually along 
the lines you describe.

For one, range creation is easy in D, consistent with the pro/con 
tradeoffs described in the thread/talk [Iterator and Ranges: 
Comparing C++ to D to 
Rust](https://forum.dlang.org/thread/diexjstekiyzgxlicnts forum.dlang.org).
Another is that if application/task specific logic is involved, it is often
simpler/faster to just incorporate it into the range rather than figure out how
to factor it out of the more general range. Especially if the range is not
going to be used much.

--Jon
Jul 06 2021
parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 7/6/21 11:42 PM, Jon Degenhardt wrote:

 On Wednesday, 7 July 2021 at 01:44:20 UTC, Steven Schveighoffer wrote:

 This is pretty minimal, but does what I want it to do. Is it ready for 
 inclusion in Phobos? Not by a longshot! A truly generic interleave 
 would properly forward everything else that the range supports (like 
 `length`, `save`, etc).

 But it got me thinking, how often do people roll their own vs. trying 
 to compose using existing Phobos nuggets? I found this pretty 
 satisfying, even if I didn't test it to death and maybe I use it only 
 in one place. Do you find it difficult to use Phobos in a lot of 
 situations to compose your specialized ranges?


 
 I try to compose using existing Phobos facilities, but don't hesitate to 
 write my own ranges. The reasons are usually along the lines you describe.
 
 For one, range creation is easy in D, consistent with the pro/con 
 tradeoffs described in the thread/talk [Iterator and Ranges: Comparing 
 C++ to D to 
 Rust](https://forum.dlang.org/thread/diexjstekiyzgxlicnts forum.dlang.org). 
 Another is that if application/task specific logic is involved, it is 
 often simpler/faster to just incorporate it into the range rather than 
 figure out how to factor it out of the more general range. Especially if 
 the range is not going to be used much.


Yeah, I agree with all this. I do try to use existing ranges/algorithms 
as much as possible. But I find it awesome you can just whip up a quick 
shim range to get work done and not worry about making it perfect for 
general consumption. Kind of like a lambda range ;)

-Steve
Jul 07 2021
prev sibling next sibling parent reply rassoc <rassoc rassoc.org> writes:
On Wednesday, 7 July 2021 at 01:44:20 UTC, Steven Schveighoffer 
wrote:

 So I have this situation where I need to split a string, then 
 where the splits are, insert a string to go between the 
 elements making a new range, all without allocating (hopefully).


Without considering the more general case, isn't that just 
splitter-joiner?

```d
import std;

auto foo(string s, string sp, string j)  nogc {
	return s.splitter(sp).joiner(j);
}

void main() {

}
```


 Looking around phobos I found inside the documentation of 
 [roundRobin](https://dlang.org/phobos/std_range.html#.roundRobin) something
that does *exactly* what I'm looking for.

 Except... the provided `interleave` function iterates the 
 original range twice, which means 2x the searching calls for 
 splitter. Why does it do this? Because `roundRobin` will keep 
 going as long as ANY range still has data left, so you need to 
 make the "interleaving" range stop when the first one stops.


Interesting! Tried it myself, shame that this doesn't quite work:

```d
import std;

auto foo(R)(string s, string sp, R r)  nogc {
     return s.splitter(sp).zip(r)
             .map!(a => a.expand.only)
             .joiner.dropBackOne.joiner; // not bidirectional
}

void main() {

}
```
Jul 07 2021
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 7/7/21 5:54 AM, rassoc wrote:

 On Wednesday, 7 July 2021 at 01:44:20 UTC, Steven Schveighoffer wrote:

 So I have this situation where I need to split a string, then where 
 the splits are, insert a string to go between the elements making a 
 new range, all without allocating (hopefully).


 
 Without considering the more general case, isn't that just splitter-joiner?


No, splitter-joiner would make a range of characters, I want a range of 
strings.


 ```d
 import std;
 
 auto foo(string s, string sp, string j)  nogc {
      return s.splitter(sp).joiner(j);
 }
 
 void main() {

 }
 ```






 
 Interesting! Tried it myself, shame that this doesn't quite work:
 
 ```d
 import std;
 
 auto foo(R)(string s, string sp, R r)  nogc {
      return s.splitter(sp).zip(r)
              .map!(a => a.expand.only)
              .joiner.dropBackOne.joiner; // not bidirectional
 }
 
 void main() {

 }
 ```


ooh, I like the zip/expand/only trick! I got this to work, and lol, I 
don't think I'd ever use this:

```d
auto interleave(R, U)(R src, U middles) if (isInputRange!R && is(U == 
ElementType!R))
{
     return zip(StoppingPolicy.shortest, src, middles.repeat)
           .map!(e => only(e.expand))
           .joiner
           .slide(2)
           .frontTransversal;
}
```

Ironically, I think it would still run the splitting algorithm 2x, 
because `slide` has to store 2 copies of the source range. And it's not 
nogc either. Hm... I bet `dropBackOne` might actually be able to work on 
a forward range if it cached one element? But that might be iffy.

-Steve
Jul 07 2021
parent reply Sebastiaan Koppe <mail skoppe.eu> writes:
On Wednesday, 7 July 2021 at 13:30:28 UTC, Steven Schveighoffer 
wrote:

 On 7/7/21 5:54 AM, rassoc wrote:

 On Wednesday, 7 July 2021 at 01:44:20 UTC, Steven 
 Schveighoffer wrote:

 So I have this situation where I need to split a string, then 
 where the splits are, insert a string to go between the 
 elements making a new range, all without allocating 
 (hopefully).


 
 Without considering the more general case, isn't that just 
 splitter-joiner?


 No, splitter-joiner would make a range of characters, I want a 
 range of strings.


Just lift each item in a range then:

```d
import std;

auto foo(string s, string sp, string j)  nogc {
      return s.splitter(sp).map!(i => only(i)).joiner(only(j));
}

void main() {


}
```
Jul 07 2021
next sibling parent Paul Backus <snarwin gmail.com> writes:
On Wednesday, 7 July 2021 at 19:52:30 UTC, Sebastiaan Koppe wrote:

 Just lift each item in a range then:

 ```d
 import std;

 auto foo(string s, string sp, string j)  nogc {
      return s.splitter(sp).map!(i => only(i)).joiner(only(j));
 }
 ```


Code golf: `map!(i => only(i))` can be shortened to `map!only`.
Jul 07 2021
prev sibling parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 7/7/21 3:52 PM, Sebastiaan Koppe wrote:

 On Wednesday, 7 July 2021 at 13:30:28 UTC, Steven Schveighoffer wrote:

 On 7/7/21 5:54 AM, rassoc wrote:

 On Wednesday, 7 July 2021 at 01:44:20 UTC, Steven Schveighoffer wrote:

 So I have this situation where I need to split a string, then where 
 the splits are, insert a string to go between the elements making a 
 new range, all without allocating (hopefully).


 Without considering the more general case, isn't that just 
 splitter-joiner?


 No, splitter-joiner would make a range of characters, I want a range 
 of strings.


 
 Just lift each item in a range then:
 
 ```d
 import std;
 
 auto foo(string s, string sp, string j)  nogc {
       return s.splitter(sp).map!(i => only(i)).joiner(only(j));
 }
 
 void main() {


 }
 ```


Thanks! This is exactly what I was reaching for. `only` is one of the 
coolest functions (I use it elsewhere too).

-Steve
Jul 07 2021
prev sibling parent Dennis <dkorpel gmail.com> writes:
On Wednesday, 7 July 2021 at 01:44:20 UTC, Steven Schveighoffer 
wrote:

 But it got me thinking, how often do people roll their own vs. 
 trying to compose using existing Phobos nuggets?


When there's not an obvious/simple way to do something by 
composing ranges, I tend to just give up and write procedural 
code instead. Yes, the resulting code is longer and more prone to 
logic bugs, but there's no limit to what you can do and it's 
easier to see what's going on at a lower level. I also don't tend 
to let composed ranges leave the function they were created in, I 
rather pass simple arrays around than complex objects depending 
on multiple inputs from different sources.

I don't know what the destination of your range is so this might 
not be applicable, but I'd probably end up writing a function 
with an OutputRange like this:
```D
void putRangeInterleaved(O, R, E)(ref O sink, R range, E 
separator) {
     import std.range.primitives: put;
     if (!range.empty) {
         put(sink, range.front);
         range.popFront();
     }
     foreach(ref elem; range) {
         put(sink, separator);
         put(sink, elem);
     }
}
```

I'm not trying to discourage anyone from writing range code, I'm 
just presenting this as an alternative in case it's useful.
Jul 09 2021