CODEWITHSUNDEEP
haskell
Mahara
Mahara

Reputation: 33

Homework: Comparing intermediate expressions with == in Haskell

I have written the code below to test whether a list is a Palindrome or not. To my surprise its not compiling with the error "No instance for (Eq a) arising from a use of == ....". My assumption is that the compiler does not know that leftHalf and rightHalf are lists. 

    isPalindrome :: [a] -> Bool
    isPalindrome [] = False
    isPalindrome xs = if (leftHalf == reverse rightHalf)
              then True
              else False
     where leftHalf = take center xs
           rightHalf = drop center xs
           center = if  even (length xs)
                       then (length xs) `div` 2
                   else ((length xs) - 1) `div` 2

1) How do I tell the compiler that leftHalf and rightHalf are lists?
2) How would I use pattern matching or other haskell language features to solve this?

EDIT: Thank you all for your input. Special mention to Matt Fenwick for the documentation link and Duri for the elegant tip. I will write the final solutions below just in case 

     isPalindrome' :: (Eq a) => [a] -> Bool
     isPalindrome' [] = False
     isPalindrome' xs = if p then True else False
                   where p = leftHalf == rightHalf
                         leftHalf = take c xs
                         rightHalf = take c (reverse xs)
                         c = div l 2
                         l = length xs

isPalindrome' can be improved like Demi pointed out

      isPalindrome'' :: (Eq a) => [a] -> Bool
      isPalindrome'' [] = False
      isPalindrome'' xs = if (reverse xs) == xs then True else False

Upvotes: 3

Views: 185

Answers (3)

demi
demi

Reputation: 5504

You should change your type to:

isPalindrome :: Eq a => [a] -> Bool

And this is really extraneous to find center, it's enough to just write xs == reverse xs - when you computing length xs you go through all the list and there is no economy.

Upvotes: 1

Matt Fenwick
Matt Fenwick

Reputation: 49095

Check out the Eq typeclass:

ghci> :i (==)
class Eq a where
  (==) :: a -> a -> Bool
  ...
    -- Defined in GHC.Classes
infix 4 ==

What you need is a type constraint on isPalindrome.

Also, this code

if (leftHalf == reverse rightHalf)
              then True
              else False

is unnecessarily long.

Upvotes: 2

pat
pat

Reputation: 12749

In order to test if two lists are equal, it must be possible to test if the items in the list are equal. Therefore, your list of type [a] must ensure that a is an instance of Eq.

Also, as a matter of style:

x = if c then True else False

can be replaced with

x = c

Upvotes: 4

Related Questions