Haskell 列表反转错误

Question

我正在为 haskell 编写一个列表反转程序。

我已经有了列表反转的想法，这导致了以下代码：

myreverse list1
 | list1 == []    = list1
 | otherwise      = (myreverse(tail list1)):(head list1)

不幸的是，上面的代码导致以下错误：

Occurs check: cannot construct the infinite type: a = [[a]]
 Expected type: [[a]]
 Inferred type: a
 In the second argument of '(:)', namely '(head list1)'
 In the expression: (myreverse(tail list1)):(head list1)

PS：当我在我编写的名为 mylast 的代码片段上运行它时，我得到了同样的错误编码如下：

mylast list
 | list == []      = []
 | otherwise       = mylast_helper(head list1)(tail list1)

mylast_helper item list2
 | list2 == []     = item
 | otherwise       = mylast_helper(head list2)(tail list2)

递归助手的其他情况下会发生错误。

编辑：感谢您的所有输入，我想我忘记提及问题的约束禁止使用 ++ 运算符。我会在以后提出问题时牢记这一点。

干杯， -紫谷

Answer 1

您使用的函数

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

带有错误类型的参数：

myReverse (tail list1) :: [a]
head list1 :: a

在您的函数中，列表 list1 必须具有类型 a。因此，第二个参数 head list1 必须具有类型 [a]。 GHC 警告您它无法构造您为其指定的类型。列表的头部在结构上小于列表的尾部，但是您告诉它列表的头部具有类型 [a]，而列表的尾部具有类型 一个。

但是，如果您仔细观察您的类型，您会发现您可以使用 将 list1 的头部附加到 myreverse 的递归调用中。 em>(++)：

myReverse xs = case (null xs) of
               True  -> xs
               False -> myReverse (tail xs) ++ [head xs]

这里

[head xs] :: [a]
myReverse (tail xs) :: [a]

与 append 的类型一致：

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

然而，还有更好的方法来实现反向。 Prelude 将 reverse 定义为左折叠（。reverse 的另一个版本可以使用右折叠来实现，并且与您的 myReverse 非常相似功能：

reverse xs = foldr (\x xs -> xs ++ [x]) [] xs

Answer 2

首先，尝试为每个函数添加签名；这将帮助编译器知道您正在尝试做什么，并尽早为您提供更好的错误消息。签名看起来像这样，例如： mylast :: [a] ->一个。然后，不要使用守卫 (|)，而是使用模式匹配通过一系列方程定义函数：

mylast :: [a] -> a
mylast (x:[]) = x
mylast (_:t) = mylast t

在 GHCi 中，您可以使用 :t 术语。这是我能给出的最好的一般建议......仔细查看类型并确保它们对于您如何使用它们有意义。

Answer 3

cons (:) 的类型是 a ->; [一]-> [a] - 换句话说，您给它一个元素，然后给它一个列表，并将该元素放在列表的开头。在最后一行中，您将执行相反的操作 - 首先列出列表，然后列出元素。要修复此问题，请将 : 更改为列表 concat 运算符 ++:

myreverse list1
  | list1 == [] = list1
  | otherwise   = (myreverse (tail list1)) ++ [head list1]

（要尝试翻译该错误，它会说“好的，的第一个参数：你给我的是一个列表，因此第二个参数需要是相同类型的元素列表，所以列表的列表......但是......你给了我一个参数是列表中元素的类型，所以我需要某种与该类型的列表列表相同的类型，但我做不到！”）

Answer 4

最终我更多地研究这个问题并自己回答。
非常感谢您的反馈。它推动我沿着正确的方向前进。

myreverse list1
 | list1 == []  = list1
 | otherwise    = myreverse_h(list1)([])

myreverse_h list1 list2
 | list1 == []  = list2
 | otherwise    = myreverse_h(tail list1)((head list1):list2)

对于更好的代码有什么评论吗？我认为它没有那么有效...