«Запоминание» значений в функциональном программировании

Я решил взять на себя задачу изучения функционального программирования. Пока что это был взрыв, и я «видел свет» как бы. К сожалению, на самом деле я не знаю ни одного функционального программиста, от которого я мог бы откинуть вопросы. Представляем Stack Exchange.

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

Я решил, что лучший способ сделать это - проиллюстрировать простую математическую функцию, например, возвести значение в степень. Теоретически, я мог бы легко сделать это с помощью встроенной функции, но это не помогло бы достичь цели примера.

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

(Далее весь псевдокод)

f(x,y) {
  int z = x;
  for(int i = 0, i < y; i++){
    x = x * z;
  }
  return x;
}

В функциональном программировании я не был уверен. Вот что я придумал:

f(x,y,z){
  if z == 'null',
    f(x,y,x);
  else if y > 1,
    f(x*z,y-1,z);
  else
    return x;
}

Это правильно? Мне нужно держать значение zв обоих случаях, но я не был уверен, как это сделать в программировании функций. Теоретически, то, как я это делал, работает, но я не был уверен, было ли это «правильно». Есть ли лучший способ сделать это?

Прежде всего, поздравляю с «увидевшим свет». Вы сделали мир программного обеспечения лучше, расширив свой кругозор.

Во-вторых, честно говоря, профессор, не разбирающийся в функциональном программировании, не сможет сказать что-нибудь полезное о вашем коде, кроме банальных комментариев, таких как «отступы смотрятся». Это не удивительно в курсе веб-разработки, так как большинство веб-разработок выполняется с использованием HTML / CSS / JavaScript. В зависимости от того, насколько вы на самом деле заботитесь об обучении веб-разработке, вы, возможно, захотите приложить усилия, чтобы изучить инструменты, которые преподает ваш профессор (хотя это может быть болезненно - я знаю по опыту).

Чтобы ответить на поставленный вопрос: если ваш императивный код использует цикл, скорее всего, ваш функциональный код будет рекурсивным.

(* raises x to the power of y *)
fun pow (x: real) (y: int) : real = 
    if y = 1 then x else x * (pow x (y-1))

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

Как примечание, нет необходимости в значении zни в вашем императивном, ни в функциональном коде, на самом деле. Вы должны были написать свою императивную функцию следующим образом:

def pow(x, y):
    var ret = 1
    for (i = 0; i < y; i++)
         ret = ret * x
    return ret

вместо того, чтобы изменить значение переменной x.

Это на самом деле просто дополнение к ответу садовника, но я хотел бы отметить, что есть название модели, которую вы видите: сворачивание.

В функциональном программировании сгиб - это способ объединить ряд значений, который «запоминает» значение между каждой операцией. Рассмотрим добавление списка номеров обязательно:

def sum_all(xs):
  total = 0
  for x in xs:
    total = total + x
  return total

Берет список значений xsи начальное состояние из 0(представленного totalв данном случае). Затем для каждого xин xs, мы объединить это значение с текущим состоянием в соответствии с некоторой операции комбинирования (в данном случае дополнение), и использовать результат в качестве нового государства. По сути, sum_all([1, 2, 3])эквивалентно (3 + (2 + (1 + 0))). Этот шаблон может быть извлечен в функцию более высокого порядка, функцию , которая принимает функции в качестве аргументов:

def fold(items, initial_state, combiner_func):
  state = initial_state
  for item in items:
    state = combiner_func(item, state)
  return state

def sum_all(xs):
  return fold(xs, 0, lambda x y: x + y)

Эта реализация foldвсе еще обязательна, но она также может быть выполнена рекурсивно:

def fold_recursive(items, initial_state, combiner_func):
  if not is_empty(items):
    state = combiner_func(initial_state, first_item(items))
    return fold_recursive(rest_items(items), state, combiner_func)
  else:
    return initial_state

Выражаясь в терминах сгиба, ваша функция просто:

def exponent(base, power):
  return fold(repeat(base, power), 1, lambda x y: x * y))

... где repeat(x, n)возвращает список nкопий x.

Многие языки, особенно те, которые ориентированы на функциональное программирование, предлагают сворачивание в своей стандартной библиотеке. Даже Javascript предоставляет его под именем reduce. В общем, если вы обнаружите, что используете рекурсию, чтобы «запомнить» значение в каком-либо цикле, вам, вероятно, понадобится сброс.

Это дополнительный ответ, чтобы помочь объяснить карты и сгибы. Для приведенных ниже примеров я буду использовать этот список. Помните, этот список неизменен, поэтому он никогда не изменится:

var numbers = [1, 2, 3, 4, 5]

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

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

Самый простой пример этого - просто добавление номера к каждому номеру в списке. Я буду использовать псевдокод, чтобы сделать его независимым от языка:

function add-two(n):
    return n + 2

var numbers2 =
    map(add-two, numbers) 

Если вы печатаете numbers2, вы увидите, [3, 4, 5, 6, 7]какой из них является первым списком с 2, добавленными к каждому элементу. Обратите внимание, что функция add-twoбыла дана mapдля использования.

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

function add-together(n1, n2):
    return n1 + n2

var sum =
    fold(add-together, 0, numbers)

Если вы напечатаете, sumвы увидите сумму списка чисел: 15.

Вот какие аргументы нужно foldсделать:

1. Это функция, которую мы даем фолду. Сгиб будет передавать функцию текущего аккумулятора и текущий элемент списка. Все, что возвращает функция, станет новым аккумулятором, который будет передан функции в следующий раз. Это то, как вы «запоминаете» значения при зацикливании в стиле FP. Я дал ему функцию, которая берет 2 числа и добавляет их.

2. Это начальный аккумулятор; то, что аккумулятор запускается, как и прежде, чем любые элементы в списке обрабатываются. Когда вы суммируете числа, какова общая сумма до того, как вы сложили все числа вместе? 0, который я передал в качестве второго аргумента.

3. Наконец, как и в случае с картой, мы также передаем список чисел для обработки.

Если сгибы все еще не имеют смысла, подумайте об этом. Когда вы пишете:

# Notice I passed the plus operator directly this time, 
#  instead of wrapping it in another function. 
fold(+, 0, numbers)

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

[1, 2, 3, 4, 5]

становится:

0 + 1 + 2 + 3 + 4 + 5
^ Note the initial accumulator being added onto the left (for a left fold).

Который равен 15.

Используйте, mapкогда вы хотите превратить один список в другой список, такой же длины.

Используйте, foldкогда вы хотите превратить список в одно значение, например суммирование списка чисел.

Как отметил @Jorg в комментариях, «одно значение» не обязательно должно быть чем-то простым, например числом; это может быть любой отдельный объект, включая список или кортеж! То, как у меня на самом деле были клики, было для меня определить карту в терминах сгиба. Обратите внимание, как аккумулятор представляет собой список:

function map(f, list):
    fold(
        function(xs, x): # xs is the list that has been processed so far
            xs.add( f(x) ) # Add returns the list instead of mutating it
        , [] # Before any of the list has been processed, we have an empty list
        , list) 

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

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

Например, в haskell у вас уже есть функция (^)в Prelude.

Или, если вы хотите сделать это более программно product (replicate y x)

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