Складки против рекурсии в Эрланге - PullRequest
Новая
       46

Складки против рекурсии в Эрланге

6 голосов
/ 30 марта 2012

В соответствии с Изучите некоторые Эрланг :

Практически любая функция, которую вы можете придумать, которая сводит списки к 1 элементу, может быть выражена в виде сгиба.[...] Это означает, что fold является универсальным в том смысле, что вы можете реализовать практически любую другую рекурсивную функцию для списков со сгибом

Моя первая мысль при написании функции, которая принимает списки и сокращаетэто к 1 элементу - использовать рекурсию.

Какие рекомендации должны помочь мне решить, использовать ли рекурсию или сгиб?

Это стилистическое соображение или есть и другие факторы (производительность, читаемость и т. Д.)?

Ответы [ 3 ]

8 голосов
/ 30 марта 2012

Лично я предпочитаю рекурсию сгибу в Erlang (в отличие от других языков, например, Haskell).Я не вижу сгиб более читабельным, чем рекурсия.Например: 

fsum(L) -> lists:foldl(fun(X,S) -> S+X end, 0, L).

или 

fsum(L) ->
    F = fun(X,S) -> S+X end,
    lists:foldl(F, 0, L).

против 

rsum(L) -> rsum(L, 0).

rsum([], S) -> S;
rsum([H|T], S) -> rsum(T, H+S).

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

lcfoo(L) -> [ X*X || X<-L, X band 1 =:= 1].

fmfoo(L) ->
  lists:map(fun(X) -> X*X end,
    lists:filter(fun(X) when X band 1 =:= 1 -> true; (_) -> false end, L)).

ffoo(L) -> lists:foldr(
    fun(X, A) when X band 1 =:= 1 -> [X|A];
      (_, A) -> A end,
    [], L).

rfoo([]) -> [];
rfoo([H|T]) when H band 1 =:= 1 -> [H*H | rfoo(T)];
rfoo([_|T]) -> rfoo(T).

Здесь перечисление выигрывает в понимании, но на втором месте рекурсивная функция, а складная версия уродлива и менее читаема.

Инаконец, неверно, что сложение происходит быстрее, чем рекурсивная версия, особенно при компиляции в собственный (HiPE) код.

Редактировать : я добавляю сложенную версию с fun в переменной по запросу: 

ffoo2(L) ->
    F = fun(X, A) when X band 1 =:= 1 -> [X|A];
           (_, A) -> A
        end,
    lists:foldr(F, [], L).

Я не понимаю, как это более читабельно, чем rfoo/1, и я обнаружил, что манипулирование с аккумулятором особенно сложнее и менее очевидно, чем прямая рекурсия.Это еще более длинный код.

7 голосов
/ 30 марта 2012
Сгибы

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

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

2 голосов
/ 30 марта 2012

Я ожидаю, что сгибание выполняется рекурсивно, поэтому вы можете попытаться реализовать некоторые из различных функций списка, таких как map или filter, с помощью fold, и посмотреть, насколько это может быть полезно.

В противном случае, если вы делаете это рекурсивно, вы можете, в основном, повторно реализовать фолд.

Научитесь использовать то, что поставляется с языком, это моя мысль.

Это обсуждение фолд и рекурсии интересно:

Простой способ разорвать фолд

Если вы посмотрите на первый абзац во введении (вы можете прочитать все его), он скажет лучше, чем я.

http://www.cs.nott.ac.uk/~gmh/fold.pdf

...