Concat方法类型说明

Question

有人可以向我解释为什么我的 concat 实现中的源列表类型不起作用吗？

conc::[[a]]->[a]
conc xs@(x1:xs')=foldr (:) [] xs

为什么源列表应该是 [a] 而不是 [[a]]？如果我想连接 [[1,2],[3,4]] 不是类型 [[a]] 而不是 [a] 并且元素类型是 [a].

我收到以下错误：

Couldn't match type `a' with `[a]'
      `a' is a rigid type variable bound by
        the type signature for:
          conc :: forall a. [[a]] -> [a]

Answer 1

实际上编译器在错误中显示了有用的提示（实际上比您发布的消息低几行）

Expected type: [a]
Actual type: [[a]]

在下面的代码中，参数确实是[[a]]类型，但结果也是[[a]]类型，这与类型定义冲突：

conc :: [[a]] -> [a]
conc xs@(x1:xs') = foldr (:) [] xs

代码中的

xs 是 [[a]] 类型，您正在使用 foldr 对其进行迭代，并将每个 [a] 类型的元素添加到列表。因此，您将收到 [[a]].

类型的列表

Answer 2

foldr (:) [] xs == xs 是任何 xs 的 True。这意味着 foldr (:) [] 是列表上的身份函数。这个事实广为人知，Haskell 的一部分知识是如此之多，以至于 foldr (:) [] 在有经验的 Haskell 程序员的脑海中自动读作 id。

查看 foldr c n 的一种方式是将 "cons"（即 (:)）替换为 c，将 [] 替换为 n , 在给定的列表中。将 (:) 替换为 (:) 并将 [] 替换为 [] 显然不会有任何改变：

[a, b, ..., z]  ==>  a : b : ... : z : []  ==  [a, b, ..., z]

另一方面，用 (++) 替换 (:)s，将使输入列表中的所有列表连接在一起成为一个：

[a, b, ..., z]  ==>  a ++ b ++ ... ++ z

这是你想要达到的目标。

所以 concat 和 foldr 的正确实现是 foldr (++) []。

Concat方法类型说明

Explanation on the type of Concat method

haskell

concat