[Haskell-beginners] Indentation of local functions

[ChengWei]

Dear all:

Do we really have better method than this version (if list is used as the
data structure):
isPalindrome xs = xs == (reverse xs)?

Since we need to get the last xs, we already has to visit all the elements,
so nothing can be saved.

To avoid the double comparisons, maybe we will use:
let l = length xs / 2 in
take l x == take l $ reverse xs

But the length function added one more extra iteration.

We could write our own reverse function to obtain the length in the same
time with reversing. But the gain is not large enough to justify the
optimization in my opinion.


Best Regards,
Cheng Wei

On Tue, Feb 17, 2009 at 7:24 AM, Miguel Pignatelli
<miguel.pignatelli at uv.es>wrote:

> 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
>>
>>
>>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20090217/751562a6/attachment.htm