无法演绎(a〜[a])

Question

我尝试编写一个函数,它接受一个子列表列表,反转子列表并返回连接的反向子列表.这是我的尝试:

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]

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

Answer 1

在等式中

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