TL;DR I couldn't figure out how to write `isPalindrome` in terms of std.algorithm.mutation.reverse

I have dabbled in D a few times over the past few years, but still pretty inexperienced. I decided to work on some project euler problems in D for fun. A problem requires detecting a palindrome. I solved this problem in C++ before with this:

bool is_palindrome(const string& str)
{
  return str == string(str.rbegin(), str.rend());
}

I found Andrei's response to a stackoverflow question here:

http://stackoverflow.com/questions/14469612/template-conflict-for-palindrome-algorithm-on-string-array

In his response, he suggests this:

bool isPalindrome(Range)(Range r)
{
    while (!r.empty) {
        if (a.front != a.back) {
          return false;
        }
        r.popFront();
        if (r.empty) {
            return true;
        }
        r.popBack();
    }
    return true;
}

I recognize it's more efficient in terms of CPU time and memory than my C++ solution, but I suspect there is a shorter expression to detect palindromes if efficiency isn't the primary concern. So I am interested in seeing implementations of `isPalindrome` that utilize `std.algorithm.mutation.reverse`, or anyone who cares to enlighten me why that might be a misguided thing to want. Thanks for reading.

On Thu, 03 Dec 2015 21:40:05 +0000, Jim Barnett wrote:

> TL;DR I couldn't figure out how to write `isPalindrome` in terms of std.algorithm.mutation.reverse
> 
> I recognize it's more efficient in terms of CPU time and memory than my C++ solution, but I suspect there is a shorter expression to detect palindromes if efficiency isn't the primary concern. So I am interested in seeing implementations of `isPalindrome` that utilize `std.algorithm.mutation.reverse`, or anyone who cares to enlighten me why that might be a misguided thing to want. Thanks for reading.

I don't think you want reverse because it works in-place; you'd need to make a copy to compare against.  std.range.retro is probably what you're looking for:

bool isPalindrome(R)(R range) if (isBidirectionalRange!R)
{
	return range.equal(range.retro);
}

Obviously this does more work than strictly necessary, but has the brevity you're looking for.

On Thursday, 3 December 2015 at 22:14:02 UTC, Justin Whear wrote:
> I don't think you want reverse because it works in-place; you'd need to make a copy to compare against.  std.range.retro is probably what you're looking for:
>
> bool isPalindrome(R)(R range) if (isBidirectionalRange!R)
> {
> 	return range.equal(range.retro);
> }
>
> Obviously this does more work than strictly necessary, but has the brevity you're looking for.

Awesome, and thank you! Clearly I need to learn more about the D type system and std.range, but this is exactly the type of answer is was looking for.

On Thursday, 3 December 2015 at 21:40:05 UTC, Jim Barnett wrote:
> Thanks for reading.

My version slightly adjusted version:


/** Returns: If range is a palindrome larger than $(D minLength).
    See also: http://forum.dlang.org/thread/dlfeiszyweafpjiocplf@forum.dlang.org#post-vpzuaqxvtdpzpeuorxdl:40forum.dlang.org
    See also: https://stackoverflow.com/questions/21849580/equality-operator-in-favour-of-std-range-equal
    TODO: Test graphemes in `string` and `wstring`.
*/
bool isSymmetric(R)(R range, size_t minLength = 0) // TODO good value for minLength?
    if (isBidirectionalRange!(R))
{
    static if (isRandomAccessRange!R) // arrays excluding `char[]` and `wchar[]`
    {
        if (range.length < minLength) { return false; }
    }
    size_t i = 0;
    while (!range.empty)
    {
        import std.range.primitives: front, back, popFront, popBack;
        if (range.front != range.back) return false;
        range.popFront(); i++;
        if (range.empty) break;
        range.popBack(); i++;
    }
    return i >= minLength;
}

unittest
{
    assert(`dallassallad`.isSymmetric);
    assert(!`ab`.isSymmetric);
    assert(`a`.isSymmetric);
    assert(`åäå`.isSymmetric);
    assert(`áá`.isSymmetric);
    assert(`åäå`.isSymmetric(3));
    assert(!`åäå`.isSymmetric(4));
    assert(``.isSymmetric);
    assert([1, 2, 2, 1].isSymmetric);
    assert(![1, 2, 2, 1].isSymmetric(5));
}
alias isPalindrome = isSymmetric;

On Thursday, 3 December 2015 at 23:42:31 UTC, Nordlöw wrote:
> On Thursday, 3 December 2015 at 21:40:05 UTC, Jim Barnett wrote:
>> Thanks for reading.
>
> My version slightly adjusted version:
>
>
> /** Returns: If range is a palindrome larger than $(D minLength).
>     See also: http://forum.dlang.org/thread/dlfeiszyweafpjiocplf@forum.dlang.org#post-vpzuaqxvtdpzpeuorxdl:40forum.dlang.org
>     See also: https://stackoverflow.com/questions/21849580/equality-operator-in-favour-of-std-range-equal
>     TODO: Test graphemes in `string` and `wstring`.
> */
> bool isSymmetric(R)(R range, size_t minLength = 0) // TODO good value for minLength?
>     if (isBidirectionalRange!(R))
> {
>     static if (isRandomAccessRange!R) // arrays excluding `char[]` and `wchar[]`
>     {
>         if (range.length < minLength) { return false; }
>     }
>     size_t i = 0;
>     while (!range.empty)
>     {
>         import std.range.primitives: front, back, popFront, popBack;
>         if (range.front != range.back) return false;
>         range.popFront(); i++;
>         if (range.empty) break;
>         range.popBack(); i++;
>     }
>     return i >= minLength;
> }
>
> unittest
> {
>     assert(`dallassallad`.isSymmetric);
>     assert(!`ab`.isSymmetric);
>     assert(`a`.isSymmetric);
>     assert(`åäå`.isSymmetric);
>     assert(`áá`.isSymmetric);
>     assert(`åäå`.isSymmetric(3));
>     assert(!`åäå`.isSymmetric(4));
>     assert(``.isSymmetric);
>     assert([1, 2, 2, 1].isSymmetric);
>     assert(![1, 2, 2, 1].isSymmetric(5));
> }
> alias isPalindrome = isSymmetric;

Interesting solution... probably worth some future analysis for me...

The `import` statement inside the `for`-loop kind of smells to me.

It's a little more generalized than I was looking for, but interesting. Your code is also searching for a threshold of symmetry. I haven't encountered a problem like that personally, but it's interesting and makes me think.

I appreciate your response.

On Friday, 4 December 2015 at 00:23:45 UTC, Jim Barnett wrote:
> The `import` statement inside the `for`-loop kind of smells to me.
>

Sorry, inside the `while` loop

On Friday, 4 December 2015 at 00:26:23 UTC, Jim Barnett wrote:
> On Friday, 4 December 2015 at 00:23:45 UTC, Jim Barnett wrote:
>> The `import` statement inside the `for`-loop kind of smells to me.
>>
>
> Sorry, inside the `while` loop

In D it's considered idiomatic, but it can also cause some very hard to detect errors from time to time... I hate it for this reason and never do it in my own code.

On Friday, 4 December 2015 at 00:50:17 UTC, Meta wrote:
> On Friday, 4 December 2015 at 00:26:23 UTC, Jim Barnett wrote:
>> On Friday, 4 December 2015 at 00:23:45 UTC, Jim Barnett wrote:
>>> The `import` statement inside the `for`-loop kind of smells to me.
>>>
>>
>> Sorry, inside the `while` loop
>
> In D it's considered idiomatic, but it can also cause some very hard to detect errors from time to time... I hate it for this reason and never do it in my own code.

Really? If it leads to "hard to detect errors", I have a hard time believing that can be "idiomatic D". I have never seen a language that encourages the user to specify dependencies inside a loop. I am hoping I misunderstood something here.

On Friday, 4 December 2015 at 00:50:17 UTC, Meta wrote:
> On Friday, 4 December 2015 at 00:26:23 UTC, Jim Barnett wrote:
>> On Friday, 4 December 2015 at 00:23:45 UTC, Jim Barnett wrote:
>>> The `import` statement inside the `for`-loop kind of smells to me.
>>>
>>
>> Sorry, inside the `while` loop
>
> In D it's considered idiomatic, but it can also cause some very hard to detect errors from time to time... I hate it for this reason and never do it in my own code.

Inside a while, I don't think, really matches the idiom's goals. By only sticking imports inside the code that makes use of them you can achieve (I've never measured it though) compilation performance improvements in code that then imports the containing module but never makes use of the code in question. Sticking the import in the middle of the code is just noisy though, you want it nearby with limited scope but otherwise out of the way.

On Friday, 4 December 2015 at 01:10:41 UTC, Jim Barnett wrote:
> Really? If it leads to "hard to detect errors", I have a hard time believing that can be "idiomatic D".

It's used throughout the standard library, granted I don't think there's any occurrences of importing inside a while loop. The issues with nested imports are well known but also hard to fix without breaking code. However, they cut down on template bloat and the standard library makes very heavy use of templates. Thus a tradeoff is made. It's usually not nested imports by themselves that create these hard to detect errors, however. It's a few different D features working in concert.

Observe the following code:

struct Test
{
	int num = 1;
	string text = `"this is a line of text"`;
	
	void printMessage()
	{
		import std.conv, std.stdio;
		
		writeln(text("My text is ", text, " and my num is ", num));
	}
}

void main()
{
	Test t;
	t.printMessage();
}

It prints: "My text is  and my num is 0"

Why the empty space? Because instead of referring to this.text inside of the printMessage method, `text` refers to std.conv.text. The nested import overrides the member variable in the outer scope.

> I have never seen a language that encourages the user to specify dependencies inside a loop. I am hoping I misunderstood something here.

Sorry, I thought you were referring more generally to nested imports. No, imports in a while loop are not encouraged; imports in a struct or a template are.