Пожалуйста, проведите меня через этот рекурсивный образец "Erlang Programming"

Question

На странице 90 «Программирование Эрланга» Чезарини и Томсона приведен пример, в котором нет подробного обсуждения. Я довольно новичок в функциональном программировании и рекурсивном мышлении, поэтому я не знаком с такими задачами.

"Например, следующая функция объединяет два списка (одинаковой длины) путем чередования их значения: "

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.

Как это работает? Спасибо!

Answer 1

пройти через это

merge([1,2],[3,4])
reverse(mergeL([1,2],[3,4],[]))
reverse(mergeR([2],[3,4],[1]))
reverse(mergeL([2],[4],[3,1]))
reverse(mergeR([], [4], [2,3,1]))
reverse(mergeL([], [], [4,2,3,1]))
reverse([4,2,3,1])
[1,3,2,4]

Всегда хорошо выполнять эти функции вручную на листе бумаги с небольшим вводом, где вы пытаетесь это понять. Вы быстро увидите, как это работает.

Answer 2

Эта функция вызывается первой:

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

Пустой список [], переданный в mergeL, является аккумулятором - отсюда и ответ. Обратите внимание, что первая функция вызывает mergeL - левое слияние.

Давайте представим, что эта функция называется так:

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

Два списка одинаковой длины. Затем эта первая функция вызывает mergeL:

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

В левом слиянии есть 2 предложения. Вызов mergeL с аргументами будет сопоставлять эти предложения в порядке сверху вниз.

Второй из этих пунктов имеет три параметра - первые два из них являются пустыми списками []. Однако при первом вызове mergeL эти два списка не пусты, это списки X и Y, поэтому первое предложение совпадает.

Позволяет разорвать спички. Это призыв к слиянию:

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

и соответствует первому предложению следующим образом:

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

Это из-за особой формы списка:

[X | Xs]

Это означает, что X соответствует заголовку списка (отдельный элемент) и делает Xs хвостом списка (списка).

Затем мы создаем новый вызов функции. Мы можем добавить значение X в начало списка Zs так же, как мы сопоставили его с шаблоном, чтобы мы получили первый вызов mergeR:

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

Последний аргумент - это список из одного элемента, вызванный добавлением элемента в начало пустого списка.

Это проносится до конца.

На самом деле последнее предложение mergeL является излишним. По определению эта функция будет исчерпана в последнем пункте mergeR (но я оставлю это как упражнение для читателя).

Answer 3

Я всегда ищу те функции, которые сначала завершат рекурсию, в этом случае:

mergeL([],[],Zs) ->  Zs.

и

mergeR([],[],Zs) ->  Zs.

оба из них в основном завершат «объединение», когда первые два параметра являются пустыми списками.

Итак, я смотрю на первый вызов функции:

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

Не обращая внимания на секунду, вы увидите, что последний параметр - пустой список. Поэтому я ожидаю, что различные функции mergeL и mergeR будут перемещать элементы этого массива в конечный параметр - и когда они все будут перемещены, функция в основном завершится (хотя, конечно, в конце концов вызовет обратную функцию)

И это именно то, что делают остальные функции:

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

берет первый элемент X и помещает его в массив Z, а

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

берет первый элемент Y и помещает его в массив Z. Вызов mergeR из mergeL и наоборот выполняет часть чередования.

Что интересно (и легко исправить), так это то, что массивы X и Y должны быть одинаковой длины, иначе вы в итоге вызовете mergeL или mergeR с пустым массивом в X или Y - и это не будет совпадать либо [X | Xs] или [Y | Ys].

А причина обратного заключается просто в относительной эффективности [X | Zs] против [Zs | ИКС]. Первый гораздо эффективнее.

Answer 4

В этом примере определены несколько состояний, через которые будет проходить рекурсия. Есть 3 «функции», которые определены: merge, mergeL и mergeR.

Списки для слияния: Xs и Ys, тогда как Z являются результатом слияния.

Слияние начнется с вызова 'слияния' и предоставления двух списков. Первым шагом является вызов mergeL с двумя списками для слияния и пустым набором результатов.

[X | Xs] занимает первый элемент списка (очень похоже на array_shift). Этот элемент добавляется к заголовку набора результатов ([X | Zs] делает это). Этот набор результатов (содержащий теперь один элемент) затем передается следующему вызову mergeR. mergeR делает то же самое, только он берет элемент из второго списка. Это поведение будет продолжаться до тех пор, пока списки, переданные в mergeL или mergeR, не пусты.

Когда mergeL или mergeR вызывается с двумя пустыми списками ([]) и набором результатов (Zs), он возвращает набор результатов (и не выполняет другой запуск, таким образом останавливая рекурсию).

Резюме:

start рекурсии - это первая строка, которая определяет 'merge'. Этот запуск приведет все в движение, вызвав первый mergeL.

Тело рекурсии * - это строки 2 и 4, которые определяют поведение или mergeL и mergeR, которые оба вызывают друг друга.

stop рекурсии определяется строками 3 и 5, которые в основном говорят все, что делать, когда в массиве больше нет элементов.

Надеюсь, это поможет!