Dear all:<br><br>Do we really have better method than this version (if list is used as the data structure):<br>isPalindrome xs = xs == (<span style="color: rgb(64, 192, 192);">reverse</span> xs)?<br><br>Since we need to get the last xs, we already has to visit all the elements, so nothing can be saved.<br>
<br>To avoid the double comparisons, maybe we will use:<br>let l = length xs / 2 in<br>take l x == take l $ reverse xs<br><br>But the length function added one more extra iteration.<br><br>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.<br>
<br><br>Best Regards,<br>Cheng Wei<br><br><div class="gmail_quote">On Tue, Feb 17, 2009 at 7:24 AM, Miguel Pignatelli <span dir="ltr"><<a href="mailto:miguel.pignatelli@uv.es">miguel.pignatelli@uv.es</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Nice!<br>
Thanks a lot for the explanation. (and to the others that have replied!)<br>
<br>
M;<br>
<br>
<br>
El 16/02/2009, a las 17:05, Daniel Fischer escribió:<div><div></div><div class="Wj3C7c"><br>
<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Am Montag, 16. Februar 2009 16:32 schrieb Miguel Pignatelli:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hi all,<br>
<br>
This is my first post in this forum, I'm pretty new to Haskell<br>
(although I have some previous experience in functional programming<br>
with OCaml).<br>
<br>
I'm trying to write the typical function that determines if a list is<br>
a palindrome.<br>
The typical answer would be something like:<br>
<br>
isPalindrome xs = xs == (reverse xs)<br>
<br>
But I find this pretty inefficient (duplication of the list and double<br>
of needed comparisons).<br>
So I tried my own version using just indexes:<br>
<br>
isPalindrome xs =<br>
isPalindrome' 0 (length xs)<br>
where isPalindrome' i j =<br>
if i == j -- line 43<br>
then True<br>
else<br>
if (xs !! i) == (xs !! (j-1))<br>
then isPalindrome' (i+1) (j-1)<br>
else False<br>
<br>
But, when trying to load this in ghci it throws the following error:<br>
<br>
xxx.hs:43:12: parse error (possibly incorrect indentation)<br>
Failed, modules loaded: none.<br>
(Line 43 is marked in the code)<br>
<br>
I seems that the definition of isPalindrome' must be in one line. So,<br>
this works as expected:<br>
<br>
isPalindrome xs =<br>
isPalindrome' 0 (length xs)<br>
where isPalindrome' i j = if i == j then True else if (xs !! i)<br>
== (xs !! (j-1)) then isPalindrome' (i+1) (j-1) else False<br>
<br>
Is there any way to make the local definition of isPalindrome' more<br>
readable?<br>
<br>
</blockquote>
<br>
Yes, it would be horrible to look at Haskell code if there weren't.<br>
The problem is that originally, the code for isPalindrome' was indented less<br>
than the function name. Specifically, the first relevant token (i.e. not<br>
whitespace or comments) after the keywords do, let, where, case ... of<br>
opens up a new scope, which lasts until something is indented less or equally<br>
far.<br>
To not suffer from e-mailing programmes behaviour regarding leading spaces on<br>
a line, I replace those with '°', then a more readable formatting of your<br>
code would be<br>
<br>
isPalindrome xs = isPalindrome' 0 (length xs)<br>
°°°where<br>
°°°°°°isPalindrome' i j<br>
°°°°°°°°°| j <= i = True<br>
°°°°°°°°°| xs !! i /= xs !! (j-1) = False<br>
°°°°°°°°°| otherwise = isPalindrome (i+1) (j-1)<br>
<br>
I have replaced your nested ifs by guards (increases readability, IMO) and<br>
corrected the stopping condition so that it also works on words of odd<br>
length.<br>
<br>
However, note that Haskell lists aren't arrays, but singly linked lists, so to<br>
find xs !! k, all the first (k+1) cells of the list must be visited, making<br>
your algorithm less efficient than the naive one, since you must visit<br>
O((length xs)^2) cells.<br>
<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Any help in understanding this would be appreciated<br>
<br>
Thanks in advance,<br>
<br>
M;<br>
</blockquote>
<br>
Cheers,<br>
Daniel<br>
<br>
<br>
</blockquote>
<br>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/beginners" target="_blank">http://www.haskell.org/mailman/listinfo/beginners</a><br>
</div></div></blockquote></div><br>