[Haskell-beginners] Indentation of local functions

[Daniel Fischer]

Am Montag, 16. Februar 2009 16:32 schrieb Miguel Pignatelli:
> 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?
>

Yes, it would be horrible to look at Haskell code if there weren't.
The problem is that originally, the code for isPalindrome' was indented less 
than the function name. Specifically, the first relevant token (i.e. not 
whitespace or comments) after the keywords do, let, where, case ... of
opens up a new scope, which lasts until something is indented less or equally 
far.
To not suffer from e-mailing programmes behaviour regarding leading spaces on 
a line, I replace those with '°', then a more readable formatting of your 
code would be

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 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.

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.

> Any help in understanding this would be appreciated
>
> Thanks in advance,
>
> M;

Cheers,
Daniel