[Haskell-beginners] Re: Indentation of local functions

Christian Maeder Christian.Maeder at dfki.de
Tue Feb 17 04:09:41 EST 2009

Daniel Fischer wrote:
> isPalindrome xs = isPalindrome' 0 (length xs)
> °°°where
> °°°°°°isPalindrome' i j
> °°°°°°°°°| j <= i 	= True
> °°°°°°°°°| xs !! i /= xs !! (j-1)	= False
> °°°°°°°°°| otherwise = isPalindrome (i+1) (j-1)

I only want to point out, that it is possible to put "where" ("do" or
"let") at the end of the previous line, but a separate line for "where"
is a good idea, too.

> I have replaced your nested ifs by guards (increases readability, IMO) and 
> corrected the stopping condition so that it also works on words of odd 
> length.

Instead of course I prefer boolean expressions in some cases:

isPalindrome xs = isPalindrome' 0 (length xs) where
  isPalindrome' i j = j <= i
    || xs !! i == xs !! (j-1)
        && isPalindrome' (i+1) (j-1)

> However, note that Haskell lists aren't arrays, but singly linked lists, so to 
> find xs !! k, all the first (k+1) cells of the list must be visited, making 
> your algorithm less efficient than the naive one, since you must visit 
> O((length xs)^2) cells.

Right, and only computing the length takes n steps, which is hard to
avoid when one wants to avoid double equality tests.

 isPalindrome xs =
  and $ zipWith (==) xs
      $ reverse $ drop (div (length xs + 1) 2) xs

Cheers Christian

More information about the Beginners mailing list