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

20

Я решил взять на себя задачу изучения функционального программирования. Пока что это был взрыв, и я «видел свет» как бы. К сожалению, на самом деле я не знаю ни одного функционального программиста, от которого я мог бы откинуть вопросы. Представляем 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в обоих случаях, но я не был уверен, как это сделать в программировании функций. Теоретически, то, как я это делал, работает, но я не был уверен, было ли это «правильно». Есть ли лучший способ сделать это?

Ucenna
источник
32
Если вы хотите, чтобы ваш пример был воспринят серьезно, пусть он решит практическую задачу, а не математическую. Это своего рода клише среди разработчиков, что «все FP хороши для решения математических задач», и если ваш пример - еще одна математическая функция, вы только укрепляете стереотип, а не делаете то, что делаете, выглядело полезным.
Мейсон Уилер,
12
Ваша попытка на самом деле довольно хороша, если принять во внимание реальные соображения. Все ваши рекурсивные вызовы являются хвостовыми вызовами , то есть функция не выполняет ничего после их вызова. Это означает, что компилятор или интерпретатор, который его поддерживает, может оптимизировать их, поэтому ваша рекурсивная функция использует фиксированный объем стековой памяти, а не объем, пропорциональный y.
8bittree
1
Большое спасибо за поддержку! Я все еще новичок в этом, так что мой псевдокод не идеален. @MasonWheeler Я думаю, в этом случае мой код не должен восприниматься всерьез. Я все еще учусь, и причина, по которой я люблю FP, в том, что это Math-y. Весь смысл моего примера - объяснить моему учителю, почему я использую FP. Он действительно не понимает, что это такое, так что это показалось мне хорошим способом показать ему преимущества.
Уценна
5
На каком языке вы планируете написать код? Не пытайтесь использовать стиль, который не подходит для языка, который вы используете.
Карстен С.
2
Возможно, полезно: en.wikipedia.org/wiki/Memoization
Итан Болкер

Ответы:

37

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

Во-вторых, честно говоря, профессор, не разбирающийся в функциональном программировании, не сможет сказать что-нибудь полезное о вашем коде, кроме банальных комментариев, таких как «отступы смотрятся». Это не удивительно в курсе веб-разработки, так как большинство веб-разработок выполняется с использованием 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.

gardenhead
источник
Ваш рекурсив powне совсем прав. Как есть, pow 3 3возвращается 81, а не 27. Это должно бытьelse x * pow x (y-1).
8bittree
3
Упс, писать правильный код сложно :) Исправлено, и я также добавил аннотации типов. @Ucenna Это должен быть SML, но я давно его не использовал, поэтому у меня может быть немного неправильный синтаксис. Слишком много чертовых способов объявить функцию, я никогда не могу вспомнить правильное ключевое слово. Помимо изменения синтаксиса, код идентичен в JavaScript.
садовник
2
@jwg Javascript имеет некоторые функциональные аспекты: функции могут определять вложенные функции, возвращать функции и принимать функции в качестве параметров; он поддерживает замыкания с лексической областью действия (но без динамической области видимости). Программист должен воздерживаться от изменения состояния и изменения данных.
Каспер ван ден Берг
1
@jwg Не существует согласованного определения «функционального» языка (ни для «императивного», «объектно-ориентированного» или «декларативного»). Я стараюсь по возможности воздерживаться от использования этих терминов. Под солнцем слишком много языков, чтобы их можно было разделить на четыре аккуратные группы.
садовник
1
Популярность - ужасная метрика, поэтому всякий раз, когда кто-то упоминает, что язык или инструмент X должны быть лучше, потому что он так широко используется, я знаю, что продолжать спор будет бессмысленно. Я больше знаком с семейством языков ML, чем лично Хаскелл. Но я также не уверен, правда ли это; Я думаю, что подавляющее большинство разработчиков не пробовали Haskell.
садовник
33

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

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

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. В общем, если вы обнаружите, что используете рекурсию, чтобы «запомнить» значение в каком-либо цикле, вам, вероятно, понадобится сброс.

разъем
источник
8
Определенно научитесь определять, когда проблему можно решить с помощью фолда или карты. В FP почти все циклы могут быть выражены в виде сгиба или карты; поэтому явная рекурсия обычно не требуется.
Карцигеникат 20.09.16
1
На некоторых языках можно просто написатьfold(repeat(base, power), 1, *)
user253751
4
Rico Kahler: scanэто, по сути, место, foldгде вместо простого объединения списка значений в одно значение, оно объединяется, и каждое промежуточное значение выкладывается обратно по пути, создавая список всех промежуточных состояний, созданных сгибом, вместо простого создания конечное состояние. Это реализуемо в терминах fold(каждая операция зацикливания есть).
Джек,
4
@RicoKahler И, насколько я могу судить, сокращения и сгибы - это одно и то же. Haskell использует термин «сгиб», тогда как Clojure предпочитает «уменьшать». Их поведение кажется мне одинаковым.
Карцигеникат 21.09.16
2
@Ucenna: это и переменная, и функция. В функциональном программировании функции - это значения, аналогичные числам и строкам - вы можете хранить их в переменных, передавать их в качестве аргументов другим функциям, возвращать их из функций и, как правило, обрабатывать их как другие значения. Так combiner_funcчто это аргумент, и sum_allон передает анонимную функцию (это lambdaбит - она ​​создает значение функции, не называя его), который определяет, как он хочет объединить два элемента вместе.
Джек,
8

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

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) 

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

Carcigenicate
источник
1
@Ucenna @Ucenna В вашем коде есть пара недостатков (вроде того, что их iникогда не определили), но я думаю, у вас есть правильная идея. Одна проблема в вашем примере: функция ( x) передает только один элемент списка за раз, а не весь список. Когда xвызывается первый раз , передается ваш начальный аккумулятор ( y) в качестве первого аргумента, а первый элемент - в качестве второго аргумента. При следующем запуске xбудет передан новый аккумулятор слева (независимо от того, что было xвозвращено в первый раз) и второй элемент списка в качестве второго аргумента.
Карцигеникат
1
@Ucenna Теперь, когда у вас есть основная идея, посмотрите снова на реализацию Джека.
Carcigenicate
1
@Ucenna: разные языки имеют разные предпочтения в отношении того, принимает ли функция, заданная для свертывания, аккумулятор в качестве первого или второго аргумента, к сожалению. Одна из причин, по которой приятно использовать коммутативную операцию типа сложения для обучения сгибам.
Джек,
3
«Используйте, foldкогда вы хотите превратить список в одно значение (например, суммирование списка чисел)». - Я просто хочу отметить, что это «единственное значение» может быть сколь угодно сложным… включая список! На самом деле, foldэто общий метод итерации, он может делать все , что может делать итерация. Например, это mapможет быть тривиально выражено как func map(f, l) = fold((xs, x) => append(xs, f(x)), [], l)Здесь, «единственное значение», вычисляемое на foldсамом деле, является списком.
Йорг Миттаг,
2
... возможно, хотите сделать со списком, можно сделать с fold. И это не обязательно должен быть список, подойдет любая коллекция, которая может быть выражена как пустая / не пустая. Что в основном означает, что подойдет любой итератор. (Я предполагаю, что добавление слова «катаморфизм» было бы слишком много для введения новичка, хотя :-D)
Йорг W Mittag
1

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

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

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

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

Виктор Меллгрен
источник
1
Чтобы логически связать этот ответ с остальными, следует отметить, что productэто просто функция ярлыка foldс умножением в качестве ее функции и 1 в качестве ее начального аргумента, и replicateэто функция, которая создает итератор (или список; как я уже отмечал) вышеупомянутые два по существу неразличимы в haskell), что дает заданное количество идентичных выходных данных. Теперь должно быть легко понять, как эта реализация делает то же самое, что и ответ @ Jack выше, просто используя предопределенные версии тех же функций для особых случаев, чтобы сделать ее более краткой.
Периата Breatta