Nice! Thanks a lot for the explanation. (and to the others that have replied!) M; El 16/02/2009, a las 17:05, Daniel Fischer escribió:
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