list - Haskell：不使用 (++) 连接列表

Question

我正在尝试编写一个函数，该函数将组合 2 个列表而不使用“分而治之”。因此我不能使用(++).

Prelude> let combineList (x:xs) (y:ys) = if null (y:ys)==True then x:xs else combineList (x:xs++[y]) (ys)

这就是我现在所拥有的，我得到了"Non-exhaustive patterns in function combineList"。我意识到问题来自if null (y:ys)==True，因为这个功能有效 -

Prelude> let combineList (x:xs) (y:ys) = if ys==[] then x:xs++[y] else combineList (x:xs++[y]) (ys)

但如果可能的话，我想去掉++[y]输出中的。

非常感谢您更正代码。

score 3 · Accepted Answer

(x:xs)不匹配任何列表。相反，它匹配带有一个 head 元素x和一个 tail的列表xs。（我猜你可以认为它匹配一个cons单元格。）null (x:xs)也不能是假的，因为 any(x:xs)不为空，基本上根据定义。

"Non-exhaustive patterns in function"表示输入无法与函数的模式匹配。在这种情况下，两个参数都不能为空，因此如果其中一个为空，则匹配失败。

因为你显然是用ifs 做的，你会想要匹配任何列表，所以函数看起来像

combineList xs ys = if null xs then ys else head xs : combineList (tail xs) ys

然而，在 haskell 中更常用的方法是分别对模式进行模式匹配nil：

cl [] ys = ys
cl (x:xs) ys = x : cl xs ys

（这等价于的定义(++)，但采用前缀形式：）

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys
 -- or         = x : (++) xs ys

它也遵循折叠模式：我们可以在第一个列表上累积 consing，第二个列表用作初始尾部：

cl' xs ys = foldr (:) ys xs

这也允许我们无意义地编写函数（即无点风格）：

cl'' = flip (foldr (:))

score 1 · Accepted Answer

警告意味着您的函数与数据类型"Non-exhaustive patterns in function `combineList`"的每个构造函数都不匹配。type 包含两个构造函数，并且; 当您使用模式匹配时，编译器假定您要匹配数据类型的每个构造函数。List(:)[]

这是一种可能的解决方案：

combineList (x:xs) ys = if null xs then x : ys else x : combineList xs ys

在 Haskell 中，一种更好的编写方法是使用模式匹配。请注意，这也是的实际定义(++)：

combineList []     ys = ys 
combineList (x:xs) ys = x : combineList xs ys

2 回答 2