6.20 Example: Testing for Palindromes

In this section we define a function pal? that tests whether its palindrome argument is a palindrome, that is, something that reads the same backwards and forwards. For example, the string ``Madam I’m Adam’’ is a palindrome (excluding blanks and punctuation) and so is the number 123454321. The definition works for any datatype that has n components that are accessed by the indices 1…n.

Here is the definition for pal?. It is simply a call to an auxiliary function called palAux?. We are following the convention of ending a function’s name with ? if the function returns a Boolean value.

pal? s == palAux?(s,1,#s)

_{Type: Void}

Here is palAux?. It works by comparing elements that are equidistant from the start and end of the object.

palAux?(s,i,j) ==
  j > i =>
    (s.i = s.j) and palAux?(s,i+1,i-1)
  true

_{Type: Void}

Try pal? on some examples. First, a string.

pal? "Oxford"

Compiling function palAux? with type (String,Integer,Integer) ->
   Boolean
Compiling function pal? with type String -> Boolean

\[\]

false

_{Type: Boolean}

A list of polynomials.

pal? [4,a,x-1,0,x-1,a,4]

Compiling function palAux? with type (List Polynomial Integer,
   Integer,Integer) -> Boolean
Compiling function pal? with type List Polynomial Integer -> Boolean

\[\]

true

_{Type: Boolean}

A list of integers from the example in the last section.

pal? [1,6,15,20,15,6,1]

Compiling function palAux? with type (List PositiveInteger,Integer,
   Integer) -> Boolean
Compiling function pal? with type List PositiveInteger -> Boolean

\[\]

true

_{Type: Boolean}

To use pal? on an integer, first convert it to a string.

pal?(1441::String)

\[\]

true

_{Type: Boolean}

Compute an infinite stream of decimal numbers, each of which is an obvious palindrome.

ones := [reduce(+,[10^j for j in 0..i]) for i in 1..]

\[\]

[11,111,1111,11111,111111,1111111,..11111111,111111111,1111111111,11111111111,…]

_{Type: Stream PositiveInteger}

)set streams calculate 9

How about their squares?

squares := [x^2 for x in ones]

\[\]

[121,12321,1234321,123454321,12345654321,1234567654321,.123456787654321,12345678987654321,1234567900987654321,.123456790120987654321,…]

_{Type: Stream PositiveInteger}

Well, let’s test them all.

[pal?(x::String) for x in squares]

\[\]

[true,true,true,true,true,true,true,true,true,true,…]

_{Type: Stream Boolean}

)set streams calculate 7