无法理解 Haskell 合并功能

Question

我有一项任务是让 Haskell 函数在不使用 ++ 操作的情况下将 2 个列表合并在一起。我在网上找到了以下代码，它按预期工作，但我需要帮助了解它的工作原理和原因。如果有人可以带我逐步了解此功能的工作原理，我将不胜感激。我对 Haskell 非常陌生，所以假设您是在向 5 岁的孩子解释这一点，哈哈。

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

Answer 1

Haskell 中的列表被定义为一个链表，[]作为空列表，并且(:)是“ cons ”，其中第一个参数是头部（第一个元素），第二个元素是尾部（因此是一个包含其余元素的列表） ）。因此，这意味着列表 like[1,4]表示为(1 : (4 : []))，或者更多 can canonical (:) 1 ((:) 4 [])。

如果我们现在想要合并两个列表[1,4]，[2,5]例如我们因此调用 merge with merge (1 : (4 : [])) (2 : (5 : []))。合并的第一条规则检查第一个参数是否为空列表，事实并非如此，因此我们继续第二条规则。这将检查第一个列表是否使用cons数据构造函数，就是这种情况。所以它x与列表的头部（这里1）和xs列表的其余部分（这里）统一[4]。因此，这意味着它将替换为：

merge (1 : (4 : [])) (2 : (5 : []))  ->  1 : merge (4 : []) (2 : (5 : []))

现在在递归调用中，将再次检查第一个子句，但(:) 4 []再次与空列表不匹配[]，因此我们检查第二个子句，再次匹配。因此，在这个调用x与相结合4，并xs用[]：

merge (4 : [])) (2 : (5 : []))  ->  4 : merge [] (2 : (5 : []))

最后一个递归将空列表数据构造函数作为第一个参数。因此，这与第一个子句中的模式匹配。因此我们返回第二个列表：

merge [] (2 : (5 : []))  ->  (2 : (5 : []))

结果是一个列表：

(1 : (4 : (2 : (5 : []))))

或简而言之：

[1,4,2,5]