在 Haskell 中反转列表的无限类型错误

Question

我正在尝试实现列表的反转：

myLast :: [a] -> a
myLast [] = error "No end for empty lists!"
myLast [x] = x
myLast (_:xs) = myLast xs

myReverse :: [a] -> [a]
myReverse (x:xs) = myLast xs + myReverse xs

但我收到此错误：

/workspaces/hask_exercises/exercises/src/Lib.hs:42:32: error:
    * Occurs check: cannot construct the infinite type: a ~ [a]
    * In the second argument of `(+)', namely `myReverse xs'
      In the expression: myLast xs + myReverse xs
      In an equation for `myReverse':
          myReverse (x : xs) = myLast xs + myReverse xs
    * Relevant bindings include
        xs :: [a] (bound at src/Lib.hs:42:14)
        x :: a (bound at src/Lib.hs:42:12)
        myReverse :: [a] -> [a] (bound at src/Lib.hs:41:1)
   |
42 | myReverse (x:xs) = myLast xs + myReverse xs
   |                                ^^^^^^^^^^^^

cannot construct the infinite type: a ~ [a]是什么意思？我经常遇到这个错误，想了解它的含义。

Answer 1

(+) :: Num a => a -> a -> a 函数将两个数字（相同类型）相加。因此，例如，如果 a ~ Int，它会将两个 Int 相加，但不会将 Int 和 [Int].

相加

但是即使 (+) 运算符将一个项目添加到列表中，它仍然不会正确地反转列表：您的函数没有 base case为空列表做什么，而您的递归列表对列表 (x:xs).

的第一项 x 没有任何作用

一个简单的反转方法：

myReverse :: [a] -> [a]
myReverse [] = []
myReverse (x:xs) = myReverse xs <b>++</b> [x]

但这效率不高：附加两个项目将花费与左侧列表大小成线性关系的时间。您可以使用累加器：每次递归调用时都会更新的参数。这看起来像：

myReverse :: [a] -> [a]
myReverse [] = go <b>[]</b>
    where go <b>ys</b> (x:xs) = …
    where go <b>ys</b> [] = …

填写 … 部分留作练习。

Answer 2

你有

myLast :: [a] -> a 
myReverse :: [a] -> [a]

myReverse (x:xs) = myLast xs    +     myReverse xs
                   \___a___/          \____[a]___/

          (x:xs)  :: [a]
          ---------------
           x      ::  a
             xs   :: [a]                        xs :: [a]               
      myLast      :: [a] -> a         myReverse    :: [a] -> [a]
     -------------------------       ----------------------------
      myLast xs   ::        a         myReverse xs ::        [a]

myReverse (x:xs)                                   ::        [a]

但是

> :t (+)
                               (+) :: Num a =>  a  ->  a  ->  a

也就是说+左边的东西的类型和右边的东西的类型必须一样

但它们不可能：正如我们刚刚在上面看到的，在您的代码中，第一个（myLast xs）是某种类型 a，第二个（myReverse xs ) 是 [a] 相同 a 的列表。

这两个不能相同，因为它意味着

              a  ~  [a]             OK, this is given to us, then
                     a  ~ [a]       we can use it, so that
                 --------------
              a  ~ [[a]]            this must hold;
                     a  ~ [a]       we know this, then
                 --------------
             a  ~ [[[a]]]           this must also hold; and
                     a  ~ [a]       ........
                 --------------     ........
             a ~ [[[[a]]]]          ........
          .........................

以此类推，如此循环往复，从而使 a 成为“无限”类型。因此错误。

您可以通过将 + 替换为

来修复它

                              (+++) ::         a  ->  [a]  ->  [a]

并实施它来完成您需要它做的事情。

您还需要修复 off-by-one 错误，即您完全忽略接收到的输入中的第一个元素 x.

在 Haskell 中反转列表的无限类型错误

infinite type error reversing a list in Haskell

haskell

types

list

infinite