Зависание рекурсивного вызова функции, Erlang

Он не завершается, потому что вы создаете новый непустой список в каждом случае: [Anything] всегда является непустым списком, даже если этот список содержит пустой список в качестве единственного элемента ([[]] является непустым списком из одного элемента ).

Правильный список заканчивается так: [ Something | [] ].

Так что с учетом этого...

list_length([])      ->   0;
list_length([_|Xs])  ->   1 + list_length(Xs).

В большинстве функциональных языков «правильные списки» представляют собой списки в стиле cons. Ознакомьтесь с статьей Википедии о "против" и документацию Erlang о списках, а затем немного поразмышляйте над примерами операций над списками, которые вы видели в примере кода.

ПРИМЕЧАНИЯ

1. Использование пробелов вокруг операторов — это хорошо; это не позволит вам делать запутанные вещи со стрелками и операторами двоичного синтаксиса рядом друг с другом, а также позволит избежать нескольких других двусмысленностей (и в любом случае его легче читать).

2. Как отмечает Стив, взрыв памяти, который вы заметили, связан с тем, что, хотя ваша функция является рекурсивной, она не является хвостовой рекурсией, то есть 1 + list_length(Xs) оставляет незавершенную работу, которая должна оставить ссылку на куча. Чтобы что-то добавить к нему 1, необходимо завершить выполнение list_length/1, вернуть значение и в этом случае запомнить это ожидающее значение столько раз, сколько элементов в списке. Прочитайте ответ Стива для примера того, как хвостовые рекурсивные функции могут быть записаны с использованием значения accumulator.

Поскольку OP изучает Erlang, обратите внимание также, что функция list_length/1 не поддается оптимизации хвостового вызова из-за его операции сложения, которая требует, чтобы среда выполнения рекурсивно вызывала функцию, брала возвращаемое значение, добавляла к нему 1 и возвращала результат. Для этого требуется место в стеке, а это означает, что если список достаточно длинный, у вас может закончиться стек.

Вместо этого рассмотрите этот подход:

list_length(L)           -> list_length(L, 0).
list_length([], Acc)     -> Acc;
list_length([_|Xs], Acc) -> list_length(Xs, Acc+1).

Этот подход, очень распространенный в коде Erlang, создает аккумулятор в list_length/1 для хранения значения длины, инициализирует его значением 0 и передает в list_length/2, который выполняет рекурсию. Затем каждый вызов list_length/2 увеличивает аккумулятор, и когда список пуст, первое предложение list_length/2 возвращает аккумулятор в качестве результата. Но обратите внимание, что операция сложения здесь происходит до рекурсивного вызова, что означает, что вызовы являются истинными хвостовыми вызовами и, таким образом, не требуют дополнительного пространства стека.

Для начинающих программистов на Erlang может быть полезно скомпилировать как исходную, так и модифицированную версии этого модуля с помощью erlc -S и изучить сгенерированный ассемблер Erlang. В исходной версии ассемблер содержит allocate вызовов для пространства стека и использует call для рекурсивного вызова, где call — инструкция для обычных вызовов функций. Но для этой модифицированной версии вызовы allocate не генерируются, и вместо использования call выполняется рекурсия с использованием call_only, которая оптимизирована для хвостовых вызовов.