помогите объяснить этот рекурсивный пример программы F #

Question

let rec aggregateList (f:int->int->int) init list = 
    match list with
    | [] -> init
    | hd::tl -> 
        let rem = aggregateList f init tl
        f rem hd

let add a b = a + b
let mul a b = a * b

//to use in F# Interactive:
//aggregateList add 0 [1..5];;

Получил этот пример из "Функционального программирования для реального мира" Томаса Петричека

Я не понимаю, во втором ответвлении в этом сопоставлении с образцом: f rem hd .Может ли кто-нибудь мне помочь?

Answer 1

Давайте сначала разберем объявление функции aggregateList. Функция принимает три параметра:

1. Функция с именем f, которая принимает два int с и возвращает третий int.
2. Начальное значение, с которого нужно начать агрегирование.
3. Список значений.

Затем функция сопоставляется со списком, которому она предоставляется, с одной из двух возможностей:

1. Список пуст, в этом случае возвращается значение init.
2. Список не пустой, в этом случае он берет первый элемент и присваивает его hd (или голове), а остальную часть списка назначает tl (или хвосту). Затем он выполняет рекурсивный вызов aggregateList f init tl. Когда это возвращается, он берет результат и присваивает его rem. Затем он вызывает f на rem и hd.

Как отмечали другие люди, это делает то же самое, что и функция List.foldback в базовой библиотеке F # .

Будьте осторожны, конечно, чтобы правильно выбрать значение init, потому что если вы выполнили aggregateList mul 0 somelist;;, вы просто получите 0 независимо от того, какой список вы предоставляете.

Answer 2

Просто для удовольствия, давайте сделаем некоторую отладку в стиле printf:

> aggregateList (fun acc x -> printf "%i " x; acc + x) 0 [1..10];;
10 9 8 7 6 5 4 3 2 1 val it : int = 55

Похоже, что функция эквивалентна List.foldBack (или fold_right на других языках): она обходит каждый элементв списке справа налево и вызывает для них функцию f.

Давайте перепишем функцию несколькими различными способами:

// functional version
let rec foldBack f seed = function
    | [] -> seed
    | x::xs -> let res = foldBack f seed xs in f res x

// imperative version
let foldBack f seed xs =
    let mutable result = seed
    for x in List.rev xs do
        result <- f result x
    result

// C# equivalent
public static U FoldBack<T, U>(Func<T, U> f, U seed, IEnumerable<T> xs) {
    foreach(T x in xs.Reverse())
        seed = f(seed, x);
    return seed;
}

Вы бы использовали функциюкак это:

let sum = foldBack (+) 0 [1..10] // returns 55
let sumOfSquares = foldBack (fun acc x -> acc + x * x) 0 [1..10];; // 385

---

Я не понимаю, во второй ветви в этом сопоставлении с образцом: f rem hd.Может ли кто-нибудь мне помочь?

Итак, давайте начнем с того, что мы уже знаем о функциях F #:

• f - это функция типа int -> int -> int.Вы передаете функции, как если бы они были любой другой переменной, например, int или строкой.
• Вы вызываете функции, передавая разделенный пробелами список аргументов.f rem hd вызывает функцию f с двумя аргументами, rem и hd.
• Последнее выражение, вычисленное в функции, обрабатывается как возвращаемое значение функции.

Возвращаясь к исходной функции:

let rec aggregateList (f:int->int->int) init list = 
    match list with
    | [] -> init
    | hd::tl -> 
        let rem = aggregateList f init tl   // 1
        f rem hd                            // 2

В строке 1 мы вызываем aggregateList рекурсивно с tl.Так как список становится все меньше и меньше, в конечном итоге мы собираемся перейти к нулевому регистру, который возвращает init.

В строке 2 f rem hd - это возвращаемое значение функции.Однако, поскольку мы возвращались к стеку, пока шли к концу списка, мы будем вызывать эту функцию по одному для каждого элемента (в порядке справа налево), когда мы возвращаемся к трассировке стека.

Учитывая aggregateList (+) 0 [1..10], нулевой регистр возвращает 0, поэтому мы вызываем:

• возвращаемое значение = f rem hd = f 0 10 = 0 +10 = 10
• возвращаемое значение = f rem hd = f 10 9 = 9 + 10 = 19
• возвращаемое значение = f rem hd =f 19 8 = 19 + 8 = 27
• возвращаемое значение = f rem hd = f 27 7 = 27 + 7 = 34
• возвращаемое значение = f rem hd = f 34 6 = 34 + 6 = 40
• возвращаемое значение = f rem hd = f 40 5 = 40 + 5 = 45
• возвращаемое значение = f rem hd = f 45 4 = 45 + 4 = 49
• возвращаемое значение = f rem hd = f 49 3 = 49 + 3 = 52
• возвращаемое значение = f rem hd = f 52 2 = 52 + 2 = 54
• возвращаемое значение = f rem hd = f 54 1 =54 + 1 = 55

В списке больше нет элементов, поэтому вся функция возвращает 55.

Как вы можете себе представить, вложенные вызовы в aggregateList оцениваются таким образом для списка длины n:

f (f (f (f (f (f (f (f init hd _n ) hd _n-1 ) hd _n-2 ) hd) _n-3 ) ... HD ₂ ) HD ₁ ) HD ₀

Answer 3

Вызывает функцию f (один из параметров), передавая ей результат рекурсивного вызова и следующий элемент.

rem - остаток, или в этом случае результат остатказначения.

hd - следующий элемент, как видно из части | hd::tl -> сопоставления с образцом.

По сути, эта агрегатная функция принимает функцию, начальную точку исписок.Способ представления строки примера:

(1 + (2 + (3 + (4 + (5 + 0)))))