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

Question

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

Prelude> letcombineList(x:xs)(y:ys) = if null(y:ys)==True then x:xs elsecombineList(x:xs++[y])(ys)

这就是我现在所拥有的，我得到“函数combineList中的非详尽模式”。我意识到问题来自 if null (y:ys)==True，因为这个函数有效 -

Prelude> letcombineList (x:xs) (y:ys) = if ys==[] then x:xs++[y] elsecombineList (x:xs++[y]) (ys)

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

非常感谢对代码的更正。

Answer 1

(x:xs) 与任何列表都不匹配。相反，它匹配具有头元素 x 和尾元素 xs 的列表。 (我猜，您可以将其视为匹配 cons 单元格。)null (x:xs) 也永远不可能为 false，因为任何 >(x:xs) 基本上根据定义不为空。

“函数中的非详尽模式” 表示输入无法与函数的模式匹配。在这种情况下，两个参数都不能为 null，因此如果其中一个为 null，则匹配失败。

由于您显然是使用 if 执行此操作，因此您需要匹配任何列表，因此该函数将如下所示

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

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

cl' xs ys = foldr (:) ys xs

这也允许我们毫无意义地编写函数(即以 pointfree 样式):

cl'' = flip (foldr (:))