请走过我这个“Erlang Programming”递归样本 [英] Please walk me through this "Erlang Programming" recursive sample

问题描述

从Cesarini和Thomson的Erlang Programming第90页，有一个没有详细讨论的例子。我是功能编程和递归思维的新手，所以我不太熟悉这样解决问题。

From page 90 of Erlang Programming by Cesarini and Thomson, there is an example that has no detailed discussion. I'm quite the newbie to functional programming and recursive thinking, so I'm not familiar in solving problems this way.

例如，以下函数合并了两个列表（相同长度）通过交织
他们的值：

"For example, the following function merges two lists (of the same length) by interleaving their values: "

merge(Xs,Ys) -> lists:reverse(mergeL(Xs,Ys,[])).

mergeL([X|Xs],Ys,Zs) ->  mergeR(Xs,Ys,[X|Zs]);
mergeL([],[],Zs) ->  Zs.

mergeR(Xs,[Y|Ys],Zs) ->  mergeL(Xs,Ys,[Y|Zs]);
mergeR([],[],Zs) ->  Zs.

这是如何工作的？谢谢！

How does this work? Thanks!

推荐答案

这个函数首先被调用：

merge(Xs,Ys) -> lists:reverse(mergeL(Xs,Ys,[])).

传递给mergeL的空列表是累加器 - 这是答案将来自的地方。请注意，第一个函数调用mergeL - 左合并。

The empty list [] passed to mergeL is the accumulator - this is where the answer will come from. Note that the first function calls mergeL - the left merge.

让我们假装这个函数是这样调用的：

Let us pretend that this function is called as so:

merge([1, 2, 3], [a, b, c])

两个长度相同的列表。这个第一个函数然后调用mergeL：

Two lists of the same length. This first function then calls mergeL:

mergeL([X|Xs],Ys,Zs) ->  mergeR(Xs,Ys,[X|Zs]);
mergeL([],[],Zs) ->  Zs.

左合并有2个子句。调用mergeL与参数将自上而下匹配这些子句。

There are 2 clauses in left merge. The call to mergeL with arguments will match these clauses in top down order.

这些子句中的第二个有三个参数 - 前两个是空列表[]。然而，第一次mergeL被称为这两个列表不是空的，它们是列表X和Y，所以第一个子句匹配。

The second of these clauses has three parameters - the first two of these are empty lists []. However the first time mergeL is called these two lists aren't empty they are the lists Xs and Ys so the first clause matches.

让我们打破匹配。这是调用mergeL：

Lets break out the matches. This is the call to mergeL:

mergeL（[1，2，3]，[a，b，c]，[]）

mergeL([1, 2, 3], [a, b, c], [])

，它以下列方式与第一个子句匹配：

and it matches the first clause in the following fashion:

X = 1
Xs = [2, 3]
Ys = [a, b, c]
Zs = []

这是因为列表的特殊形式：

This is because of the special form of the list:

[X | Xs]

这意味着将X匹配到列表的头部（单个项目），并将Xs列表的尾部（一个列表）。

This means match X to the head of the list (an individual item) and make Xs the tail of the list (a list).

然后我们建立新的函数调用。我们可以将值X添加到列表Zs的开头，与我们模式匹配的方式相同，所以我们得到第一个mergeR调用：

We then build up the new function call. We can add the value X to the start of the list Zs the same way we pattern matched it out so we get the first mergeR call:

mergeR（[2，3 ]，[a，b，c]，[1]）

mergeR([2, 3], [a, b, c], [1])

最后一个参数是通过在空列表的头部添加项目而导致的单项列表

The final argument is a one-item list caused by adding an item at the head of an empty list.

这个引用直到结束。

实际上，mergeL的最后一个子句是多余的。根据定义，这个函数将在mergeR的最后一个子句中使用（但是我将把它作为读者的练习）。

Actually the final clause of mergeL is redundant. By definition this function will exhaust in the final clause of mergeR (but I will leave that as an exercise for the reader).

这篇关于请走过我这个“Erlang Programming”递归样本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！