Template Conflict for Palindrome Algorithm on String (Array)

Question

After having viewed the excellent Three Unlikely Successful Features of D by Andrei Alexandrescu I tested the palindrome algorithms given there as follows

import std.exception;

bool isPalindrome(T)(T[] a)
{
  for (; a.length > 1; a = a[1 .. $-1]) {
    if (a[0] != a[$-1]) {
      return false;
    }
  }
  return true;
}

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

unittest {
  enforce(isPalindrome("dallassallad"));
}

The array version works fine on strings but when I add the range-version to the same compilation unit DMD (2.062) complains:

palindrome.d(31): Error: template palindrome.isPalindrome matches
more than one template declaration,
palindrome.d(10):isPalindrome(T)(T[] a) and
palindrome.d(20):isPalindrome(Range)(Range r)

My guess is to limit the use of the range to not include the array case. How do I do that?

I also tested to remove the array version but then I get the error

/home/per/Work/cognia/palindrome.d(22): Error: no property 'empty' for type 'string'
/home/per/Work/cognia/palindrome.d(22): Error: undefined identifier 'popFront'
/home/per/Work/cognia/palindrome.d(22): Error: undefined identifier 'popBack'
/home/per/Work/cognia/palindrome.d(23): Error: undefined identifier a, did you mean variable r?
/home/per/Work/cognia/palindrome.d(23): Error: undefined identifier a, did you mean variable r?
/home/per/Work/cognia/palindrome.d(27): Warning: statement is not reachable
/home/per/Work/cognia/palindrome.d(31): Error: template instance palindrome.isPalindrome!(string) error instantiating

I seems the range-version doesn't work for arrays which I find strange.

What to do?

Answer 1

Add a template constraint to the second template like so:

bool isPalindrome(Range)(Range r)
    if (!isArray!Range)

You will need to import std.traits for the isArray template.

If you want to use only the second template you will have to import std.array which uses UFCS (Uniform Function Call Syntax) to enable arrays to have the front, popFront, empty, etc, functionality.

UFCS basically means that:

int[] x;
int f = x.front;

Is translated into:

int f = front(x);

front and others are defined for arrays in std.array, which enables you to use arrays as if they are ranges. You can use the same technique for your own types. You can define the range functions such as front inside a struct/class, or you can define them externally as functions which take your struct/class as their first paramater.

See the docs for std.range for more info.

Answer 2

Also please note there's an embarrassing bug in the generic version as it might try to reduce an empty range. A corrected version is:

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;
}