CODEWITHSUNDEEP
haskell
doug
doug

Reputation: 41

beginner haskell programmer

isPalindrome::(Eq a) => [a] -> Bool
isPalindrome [] = True
isPalindrome [x] = True
isPalindrome (x1:xs:x2:[]) 
    | x1 == x2 = isPalindrome xs
    |otherwise = False


[1 of 1] Compiling Main             ( myHas.hs, interpreted )

myHas.hs:37:27:
    Couldn't match expected type `[a]' against inferred type `a1'
      `a1' is a rigid type variable bound by
           the type signature for `isPalindrome' at myHas.hs:33:18
    In the first argument of `isPalindrome', namely `xs'
    In the expression: isPalindrome xs
    In the definition of `isPalindrome':
        isPalindrome (x1 : xs : x2 : [])
                       | x1 == x2 = isPalindrome xs
                       | otherwise = False

I'm a beginner haskell programmer and got no clue as to why I'm getting this error, any help please?

Upvotes: 4

Views: 359

Answers (3)

Axman6
Axman6

Reputation: 907

I feel that an explanation of the syntax used for lists is needed here, which hasn't been given so far. firstly, the definition of the list type in Haskell is:

data [a] = a : [a] | []

Which says that a list is either empty ([]) or it is made from the (:) constructor, which has as its left argument an a, and another list (the [a] in the definition). This means that the list [1,2,3] is actually 1 : (2 : (3 : [])), but this can also be written as just 1 : 2 : 3 : [].

When pattern matching on a list, you're matching on these constructors:

f [] = … -- match the empty list

f (x:[]) = … -- match a list with one element, which you name x

f (x:xs) = … -- match the first element of the list, and whatever the rest of 
             -- the list is, but it must have at least one element. if you call
             -- f [1,2,3], x will be bound to 1, and xs will be bound to [2,3]
             -- because [1,2,3] is the same as (1:[2,3])

f (x:y:xs) = … -- matches a list with at least two elements, which you 
               -- call x and y respectively

f (xs:ys:zs:things) = … -- matches a list with at least three elements,
                        -- which you name, xs, ys and zs.

So from this, hopefully it's now clear that

f (x1:xs:x2:[])

matches a list with exactly three elements, which you name x1, xs and x2.

I hope that helps.

Upvotes: 5

Landei
Landei

Reputation: 54574

Here is an easy to understand answer, similar to your attempt:

isPalindrome [] = True
isPalindrome [x] = True
isPalindrome xs = (head xs == last xs) && isPalindrome (init (tail xs))

So an empty or one-element list is a palindrome, and a longer list is an palindrome if the first and last element are equal, and the elements "in the middle" are a palindrome as well.

Note that MGwynne's answer is much more performant, as the solution above has to traverse the list in every step.

Upvotes: 7

MGwynne
MGwynne

Reputation: 3522

You treat xs like a list, but (x1:xs:x2:[]) assumes it is an element of your input list.

Note that (x1:xs:x2:[]) will match only lists with 3 elements, and x1, xs and x2 will be elements of type a.

So xs is of type a, but as you pass it to isPalindrome, we can only assume it must be a list of something, so the type system calls the type [a1].

The easiest way to encode what you want is:

isPalindrome::(Eq a) => [a] -> Bool
isPalindrome l = l == (reverse l)

Upvotes: 13

Related Questions