Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Indentation of local functions (Andrew Wagner)
2. Re: Indentation of local functions (Daniel Fischer)
3. Palindromic solution?? (Alan Cameron)
4. Re: Palindromic solution?? (Miguel Pignatelli)
5. Re: Palindromic solution?? (Thomas Davie)
----------------------------------------------------------------------
Message: 1
Date: Mon, 16 Feb 2009 10:58:36 -0500
From: Andrew Wagner <[email protected]>
Subject: Re: [Haskell-beginners] Indentation of local functions
To: Miguel Pignatelli <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Here's one solution:isPalindrome xs =
isPalindrome' 0 (length xs)
where isPalindrome' i j = if i == j then True else check i j
check i j = if (xs !! i) == (xs !! (j-1)) then recurse i j
else False
recurse i j = isPalindrome' (i+1) (j-1)
On Mon, Feb 16, 2009 at 10:32 AM, Miguel Pignatelli <[email protected]
> wrote:
> 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?
>
> Any help in understanding this would be appreciated
>
> Thanks in advance,
>
> M;
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20090216/f2a8e955/attachment-0001.htm
------------------------------
Message: 2
Date: Mon, 16 Feb 2009 17:05:19 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Indentation of local functions
To: Miguel Pignatelli <[email protected]>, [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
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
------------------------------
Message: 3
Date: Mon, 16 Feb 2009 16:26:14 -0000
From: "Alan Cameron" <[email protected]>
Subject: [Haskell-beginners] Palindromic solution??
To: <[email protected]>
Message-ID: <777d4a2044b74d3582301b660dfac...@alanxps>
Content-Type: text/plain; charset="us-ascii"
>Date: Mon, 16 Feb 2009 16:32:23 +0100
>From: Miguel Pignatelli <[email protected]>
>Subject: [Haskell-beginners] Indentation of local functions
>To: [email protected]
>Message-ID: <[email protected]>
>Content-Type: text/plain; charset="us-ascii"
>
>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?
>
>Any help in understanding this would be appreciated
>
>Thanks in advance,
>
I have found one solution to your problem
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
This loads without error but poses a second problem it generates an index
too large exception.
Alan Cameron
------------------------------
Message: 4
Date: Mon, 16 Feb 2009 17:32:55 +0100
From: Miguel Pignatelli <[email protected]>
Subject: Re: [Haskell-beginners] Palindromic solution??
To: [email protected]
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed; delsp=yes
Yes, the index too large exception is a bug in my original code, it
should check for "i >= j" instead of "i==j"
Thanks,
M;
El 16/02/2009, a las 17:26, Alan Cameron escribió:
>> Date: Mon, 16 Feb 2009 16:32:23 +0100
>> From: Miguel Pignatelli <[email protected]>
>> Subject: [Haskell-beginners] Indentation of local functions
>> To: [email protected]
>> Message-ID: <[email protected]>
>> Content-Type: text/plain; charset="us-ascii"
>>
>> 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?
>>
>> Any help in understanding this would be appreciated
>>
>> Thanks in advance,
>>
> I have found one solution to your problem
>
> 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
>
> This loads without error but poses a second problem it generates an
> index
> too large exception.
>
>
>
>
> Alan Cameron
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
------------------------------
Message: 5
Date: Mon, 16 Feb 2009 19:04:18 +0100
From: Thomas Davie <[email protected]>
Subject: Re: [Haskell-beginners] Palindromic solution??
To: [email protected]
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=WINDOWS-1252; format=flowed;
delsp=yes
On 16 Feb 2009, at 17:26, Alan Cameron wrote:
>> Date: Mon, 16 Feb 2009 16:32:23 +0100
>> From: Miguel Pignatelli <[email protected]>
>> Subject: [Haskell-beginners] Indentation of local functions
>> To: [email protected]
>> Message-ID: <[email protected]>
>> Content-Type: text/plain; charset="us-ascii"
>>
>> 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?
>>
>> Any help in understanding this would be appreciated
>>
>> Thanks in advance,
Of note by the way the new solution is less efficient than the old
one, for each letter that it compares it must traverse the list to
find the (j-1)'th element. We can get a nice efficient solution by
simply using the take function:
isPalindrome xs = take l xs == (take l $ reverse xs)
where l = length xs `div` 2
Bob
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 8, Issue 14
****************************************
