## digitalmars.D.learn - Palindromes

• Jim Barnett (34/34) Dec 03 2015 TL;DR I couldn't figure out how to write `isPalindrome` in terms
• Justin Whear (10/19) Dec 03 2015 I don't think you want reverse because it works in-place; you'd need to
• Jim Barnett (4/13) Dec 03 2015 Awesome, and thank you! Clearly I need to learn more about the D
• =?UTF-8?B?Tm9yZGzDtnc=?= (44/45) Dec 03 2015 My version slightly adjusted version:
• Jim Barnett (9/55) Dec 03 2015 Interesting solution... probably worth some future analysis for
• Jim Barnett (2/4) Dec 03 2015 Sorry, inside the `while` loop
• Meta (4/9) Dec 03 2015 In D it's considered idiomatic, but it can also cause some very
• Jim Barnett (5/15) Dec 03 2015 Really? If it leads to "hard to detect errors", I have a hard
• Meta (35/40) Dec 03 2015 It's used throughout the standard library, granted I don't think
• Jim Barnett (7/13) Dec 03 2015 That's interesting food for thought. At this point, I am just
• Brad Anderson (8/18) Dec 03 2015 Inside a while, I don't think, really matches the idiom's goals.
• =?UTF-8?Q?Ali_=c3=87ehreli?= (26/27) Dec 03 2015 In addition to what others have explained, local imports are necessary
Jim Barnett <james.barnett.jr gmail.com> writes:
```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
```
Dec 03 2015
Justin Whear <justin economicmodeling.com> writes:
```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.
```
Dec 03 2015
Jim Barnett <james.barnett.jr gmail.com> writes:
```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.

type system and std.range, but this is exactly the type of answer
is was looking for.
```
Dec 03 2015
=?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
```On Thursday, 3 December 2015 at 21:40:05 UTC, Jim Barnett wrote:

/** Returns: If range is a palindrome larger than \$(D minLength).
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(!`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;
```
Dec 03 2015
Jim Barnett <james.barnett.jr gmail.com> writes:
```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:

/** Returns: If range is a palindrome larger than \$(D
minLength).
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(!`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.

```
Dec 03 2015
Jim Barnett <james.barnett.jr gmail.com> writes:
```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
```
Dec 03 2015
Meta <jared771 gmail.com> writes:
```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.
```
Dec 03 2015
Jim Barnett <james.barnett.jr gmail.com> writes:
```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.
```
Dec 03 2015
Meta <jared771 gmail.com> writes:
```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
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.
```
Dec 03 2015
Jim Barnett <james.barnett.jr gmail.com> writes:
```On Friday, 4 December 2015 at 03:33:55 UTC, Meta wrote:
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.

That's interesting food for thought. At this point, I am just
trying trying to transliterate my C++ and Ruby solutions for
project Euler problems to D, and trying to get a better grasp on
the D type system. Compile-time optimization isn't of much
interest to me right now, but I am glad you pointed out that is
something else to consider.
```
Dec 03 2015
```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.
```
Dec 03 2015
=?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
```On 12/03/2015 04:23 PM, Jim Barnett wrote:

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

In addition to what others have explained, local imports are necessary
for template mixins:

http://ddili.org/ders/d.en/mixin.html#ix_mixin.import,%20local

Quoting:

module a;

import std.string;    // ← wrong place

mixin template A(T) {
string a() {
T[] array;
// ...
return format("%(%s, %)", array);
}
}

"if std.string is not imported at the actual mixin site, then the
compiler would not be able to find the definition of format() at that point"

module a;

mixin template A(T) {
string a() {
import std.string;    // ← right place

T[] array;
// ...
return format("%(%s, %)", array);
}
}

Ali
```
Dec 03 2015