Эрланг: Можно ли это сделать без списков? - PullRequest
Новая
       13

Эрланг: Можно ли это сделать без списков?

7 голосов
/ 30 мая 2011

Я новичок в изучении Erlang.После прочтения о списочном понимании и рекурсии в Erlang, я хотел попытаться реализовать мою собственную map функцию, которая получилась так: 

% Map: Map all elements in a list by a function
map(List,Fun) -> map(List,Fun,[]).
map([],_,Acc) -> lists:reverse(Acc);
map([H|T],Fun,Acc) -> map(T,Fun,[Fun(H)|Acc]).

Мой вопрос таков: неправильно составлять списокчерез рекурсивную функцию, а затем поверните ее в конце.Есть ли способ построить список в правильном порядке, поэтому нам не нужно обратное?

Ответы [ 2 ]

21 голосов
/ 30 мая 2011

Чтобы понять, почему накопление и обращение происходит достаточно быстро, вы должны понять, как создаются списки в Erlang. Списки Erlangs, подобные спискам в Lisp, построены из cons-ячеек (посмотрите на картинку в ссылке).

В односвязном списке, таком как списки Эрланга, очень дешево добавить элемент (или короткий список). Это была конструкция List = [H|T].

Перевернуть односвязный список, состоящий из cons-ячеек, довольно быстро, поскольку вам нужно всего лишь один проход по списку, просто добавив следующий элемент к вам уже полностью измененный частичный результат. И, как уже упоминалось, он также реализован на C в Erlang.

Кроме того, построение результата в обратном порядке часто может быть выполнено с помощью хвостовой рекурсивной функции, которая означает, что стек не создается и ( только в старых версиях Erlang! ), поэтому некоторая память может быть сохранена.

Сказав все это: это один из Восьми мифов о производительности Эрланга , который всегда лучше встроить обратно в хвостовую рекурсивную функцию и вызвать lists:reverse/1 в конце.

Вот рекурсивная версия тела без lists:reverse/1, которая использовала бы больше памяти в версиях Erlang до 12, но не в текущих версиях: 

map([H|T], Fun) ->
    [ Fun(H) | map(T,Fun) ];
map([],_) -> [].

А вот версия карты с использованием списочных представлений: 

map(List, Fun) ->
    [ Fun(X) || X <- List ].

Как вы можете видеть, это так просто, потому что map - это просто встроенная часть понимания списка, поэтому вы могли бы использовать понимание списка напрямую и больше не нуждаться в map.

В качестве дополнительной чистой реализации Erlang, которая показывает, как эффективно работает обращение списка cons-ячеек (в Erlang всегда быстрее вызывать lists:reverse/1, потому что он в C, но делает то же самое). 

reverse(List) ->
    reverse(List, []).

reverse([H|T], Acc) ->
    reverse(T, [H|Acc]);
reverse([], Acc) ->
    Acc.

Как вы можете видеть, в списке есть только [A|B] операций, разбирая минусы (при сопоставлении с образцом) и создавая новые при выполнении [H|Acc].

0 голосов
/ 30 мая 2011
  1. Такая конструкция [Элемент |Acc], а затем перечисляет: reverse (Acc) - довольно распространенный шаблон в функциональном программировании.
  2. Вы можете написать код с аккумулятором, хранящим данные в правильном порядке, но этот код будет медленнее, чем тот, который задан в вашем вопросе (подсказка: используйте Acc ++ [Fun (H)]).
  3. На самом деле в списках Эрланга: в C реализовано обратное, и оно работает довольно быстро.
...