programador haskell principiante

Question

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 

Soy un programador principiante de Haskell y no tengo ni idea de por qué estoy recibiendo este error, ¿alguna ayuda por favor?

Answer 1

Trata xs como una lista, pero (x1:xs:x2:[]) asume que es un elemento de su lista de entrada.

Tenga en cuenta que (x1:xs:x2:[]) sólo coincidirá con las listas con 3 elementos, y x1, xs y x2 serán elementos de tipo a.

Así xs es de tipo a, pero a medida que pasan a isPalindrome, sólo podemos suponer que debe ser una lista de algo, por lo que el sistema de tipo de llama del tipo [a1].

La forma más fácil de codificar lo que quiere decir:

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

Answer 2

Aquí es un fácil de entender respuesta, similar a su intento:

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

Así una lista vacía o de un elemento es un palíndromo, y una lista más larga es un palíndromo si el primero y el último elemento son iguales, y los elementos "en el medio" también son un palíndromo.

Tenga en cuenta que la respuesta de MGwynne es mucho más rendimiento, ya que la solución anterior tiene que atravesar la lista en cada paso.

Answer 3

siento que es necesaria una explicación de la sintaxis utilizada para las listas de aquí, que no se ha dado hasta el momento. En primer lugar, la definición del tipo de lista en Haskell es:

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

que dice que una lista está vacía ([]) o que está hecho de la (:) constructor, que tiene como argumento izquierdo un a, y otra lista ([a] en la definición). Esto significa que la lista es en realidad [1,2,3]1 : (2 : (3 : [])), pero esto también se puede escribir como acaba 1 : 2 : 3 : [].

Cuando coincidencia de patrones en una lista, que está a juego en estos constructores:

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. 

Así que a partir de esto, es de esperar que ahora es claro que

f (x1:xs:x2:[]) 

coincide con una lista con exactamente tres elementos, que nombras x1, xs y x2.

Espero que ayude.