Palindromic solution??

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Palindromic solution??

Alan Cameron
>Date: Mon, 16 Feb 2009 16:32:23 +0100
>From: Miguel Pignatelli <[hidden email]>
>Subject: [Haskell-beginners] Indentation of local functions
>To: [hidden email]
>Message-ID: <[hidden email]>
>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


Reply | Threaded
Open this post in threaded view
|

Palindromic solution??

Miguel Pignatelli
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 <[hidden email]>
>> Subject: [Haskell-beginners] Indentation of local functions
>> To: [hidden email]
>> Message-ID: <[hidden email]>
>> 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
> [hidden email]
> http://www.haskell.org/mailman/listinfo/beginners
>

Reply | Threaded
Open this post in threaded view
|

Palindromic solution??

Thomas Davie
In reply to this post by Alan Cameron

On 16 Feb 2009, at 17:26, Alan Cameron wrote:

>> Date: Mon, 16 Feb 2009 16:32:23 +0100
>> From: Miguel Pignatelli <[hidden email]>
>> Subject: [Haskell-beginners] Indentation of local functions
>> To: [hidden email]
>> Message-ID: <[hidden email]>
>> 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
Reply | Threaded
Open this post in threaded view
|

Palindromic solution??

Dave Bayer
Here's a solution harder on the machine, easier on the brain:

isPalindrome :: Eq a => [a] -> Bool
isPalindrome xs = and $ zipWith (==) xs $ reverse xs

On Feb 16, 2009, at 1:04 PM, Thomas Davie wrote:

> isPalindrome xs = take l xs == (take l $ reverse xs)
>  where l = length xs `div` 2

Reply | Threaded
Open this post in threaded view
|

Palindromic solution??

Thomas Davie

On 16 Feb 2009, at 19:30, Dave Bayer wrote:

> Here's a solution harder on the machine, easier on the brain:
>
> isPalindrome :: Eq a => [a] -> Bool
> isPalindrome xs = and $ zipWith (==) xs $ reverse xs

Lets just tidy that up a little...
isPalindrome = (and . zipWith (==)) <*> reverse

But I don't see how either is easier on the brain than xs == reverse xs.

Bob