2

我尝试编写一个函数，它接受一个子列表列表，反转子列表并返回串联的反转子列表。这是我的尝试：

conrev :: Ord a => [[a]] -> [a]
conrev [[]] = []
conrev [[a]] = reverse [a]
conrev [(x:xs)] = reverse x ++ conrev [xs]

main = putStrLn (show (conrev [[1,2],[],[3,4]]))

我收到此错误：

3.hs:4:27:
    Could not deduce (a ~ [a])
    from the context (Ord a)
      bound by the type signature for conrev :: Ord a => [[a]] -> [a]
      at 3.hs:1:11-31
      `a' is a rigid type variable bound by
      the type signature for conrev :: Ord a => [[a]] -> [a] at 3.hs:1:11
    In the first argument of `reverse', namely `x'
    In the first argument of `(++)', namely `reverse x'
    In the expression: reverse x ++ conrev [xs]

我究竟做错了什么？第二个问题是 - 类型签名可以更通用吗？我必须写得尽可能通用。

4

2 回答 2

6

在等式中

conrev [(x:xs)] = reverse x ++ conrev [xs]

你匹配一个包含单个元素的列表，这是一个非空列表x:xs。所以，给定类型

conrev :: Ord a => [[a]] -> [a]

该列表x:xs必须具有类型[a]，因此x :: a。

现在，您调用reverse x，这意味着x必须是一个列表，x :: [b]。然后你连接

reverse x :: [b]

和

conrev [xs] :: [a]

从中得出b必须与 的类型相同a。但早先已经确定了a ~ [b]。总而言之，等式要求a ~ [a]。

如果你没有写（不必要的）Ord a约束，你会得到不那么不透明

Couldn't construct infinite type a = [a]

错误。

如果您删除了一些外部，您的实现将起作用[]：

conrev :: Ord a => [[a]] -> [a]
conrev [] = []
conrev [a] = reverse a
conrev (x:xs) = reverse x ++ conrev xs

但更好的实现是

conrev = concat . map reverse
于 2013-01-08T20:43:31.763 回答
3

您的第二个模式与您想要的不匹配，看起来您将类型的结构误认为是值的结构。

[[a]]作为类型的意思是“某种类型的列表的列表a”

[[a]]作为模式意味着“匹配包含单个列表的列表，该列表包含将绑定到名称的单个元素。 a

编辑：如果我理解你想要做的中间情况实际上是多余的。第三种情况将处理非空列表，第一种情况将处理空列表。没有必要为单例列表制作另一种情况。

编辑2：

第三种情况的执行还有一个问题。

conrev :: Ord a => [[a]] -> [a]
conrev [(x:xs)] = reverse x ++ conrev [xs]

给定您看到的类型，它x必须是 type[a]并且xs必须是 type [[a]]。所以写作conrev [xs]是将一个类型的值传递[[[a]]]给conrev. 这是您的类型错误的来源。您隐含地声明它与调用[a]相同的类型。aconvrev [xs]

于 2013-01-08T20:25:13.407 回答