[Haskell-beginners] Palindromic solution??

[Thomas Davie]

On 16 Feb 2009, at 17:26, Alan Cameron wrote:

>> Date: Mon, 16 Feb 2009 16:32:23 +0100
>> From: Miguel Pignatelli <miguel.pignatelli at uv.es>
>> Subject: [Haskell-beginners] Indentation of local functions
>> To: beginners at haskell.org
>> Message-ID: <90C28A9E-A67D-47CA-8416-5F1C5C27A1F9 at uv.es>
>> Content-Type: text/plain; charset="us-ascii"
>>
>> Hi all,
>>
>> This is my first post in this forum, I'm pretty new to Haskell  
>> (although I
>> have some previous experience in functional programming with OCaml)
>>
>> I'm trying to write the typical function that determines if a list  
>> is a
>> palindrome.
>> the typical answer would be something like:
>>
>> isPalindrome xs = xs == (reverse xs)
>>
>> But I find this pretty inefficient (duplication of the list and  
>> double of
>> needed comparisons).
>> So I tried my own version using just indexes:
>>
>> isPalindrome xs =
>>  	isPalindrome' 0 (length xs)
>>  	where isPalindrome' i j =
>>            if i == j   -- line 43
>>            then True
>>            else
>>            	if (xs !! i) == (xs !! (j-1))
>>            	then isPalindrome' (i+1) (j-1)
>>            	else False
>>
>> But, when trying to load this in ghci it throws the following error:
>>
>> xxx.hs:43:12: parse error (possibly incorrect indentation) Failed,  
>> modules
>> loaded: none.
>> (Line 43 is marked in the code)
>>
>> I seems that the definition of isPalindrome' must be in one line.  
>> So, this
>> works as expected:
>>
>> isPalindrome xs =
>>  	isPalindrome' 0 (length xs)
>>  	  where isPalindrome' i j = if i == j then True else if (xs !! i)  
>> ==
> (xs !! (j-1)) then isPalindrome' (i+1) (j-1) else False
>>
>> Is there any way to make the local definition of isPalindrome' more
>> readable?
>>
>> Any help in understanding this would be appreciated
>>
>> Thanks in advance,

Of note by the way – the new solution is less efficient than the old  
one, for each letter that it compares it must traverse the list to  
find the (j-1)'th element.  We can get a nice efficient solution by  
simply using the take function:

isPalindrome xs = take l xs == (take l $ reverse xs)
   where l = length xs `div` 2

Bob