初学Haskell的程序员

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

我是一名初学Haskell的程序员，对于为什么会出现这个错误毫无头绪，请帮忙解决一下吗？

- doug

Answer 1

你像对待一个列表一样处理了 xs，但是 (x1:xs:x2:[]) 假设它是输入列表中的一个元素。

请注意，(x1:xs:x2:[]) 仅匹配具有3个元素的列表，并且 x1、xs 和 x2 将是类型为 a 的元素。

因此，xs 的类型是 a，但是当把它传递给 isPalindrome 时，我们只能假定它必须是某种东西的列表，所以类型系统称其为 [a1] 类型。

编码您想要实现的最简单的方法是：

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

- MGwynne

Answer 2

这里有一个易于理解的答案，类似于您的尝试：

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

如果一个列表是空的或者只有一个元素，那么它就是一个回文列表。如果一个列表长度大于1，并且第一个元素和最后一个元素相等，那么这个列表就是一个回文列表，同时“中间”的元素也必须是一个回文列表。

需要注意的是，MGwynne的答案要比上面的解决方案性能更高，因为上面的解决方案每一步都需要遍历整个列表。

- Landei

---

如果您提供类似于问题的答案，并解释为什么不使用它，我会给您+1分！ - MGwynne

Answer 3

我觉得这里需要解释一下列表的语法，迄今为止还没有给出。首先，Haskell中列表类型的定义如下：

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

这段文字讲述了关于列表的定义和模式匹配。列表要么为空（[]），要么由构造器（:）组成，其左侧参数是a，右侧参数是另一个列表（定义中的[a]）。这意味着列表[1,2,3]实际上是1 : (2 : (3 : []))，但也可以写成1 : 2 : 3 : []。

在列表的模式匹配中，你会匹配这些构造器：

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.

所以，希望现在清楚了，这表明

f (x1:xs:x2:[])

匹配恰好有三个元素的列表，你可以将它们命名为x1、xs和x2。

希望这可以帮到你。

- Axman6