Советы по обучению "Как думать функционально"?

Question

Как новичок в функциональных языках (я начал трогать Эрланга пару недель назад - первый функциональный язык, который я мог заполучить).

Я начал писать небольшие алгоритмы (например, left_rotate_list, bubble_sort, merge_sort и т. Д.). Я часто теряюсь в таких решениях, как «использовать ли вспомогательный список для хранения промежуточных результатов?» и "я должен создать вспомогательную функцию, чтобы сделать это?"

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

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

Спасибо за комментарии. Да, я хочу получить совет о том, как «мыслить на функциональном языке» (так же, как «думать на Java», «думать на C ++»).

Answer 1

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

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

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

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

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

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

Answer 2

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

Ну, на самом деле это не дизайн сверху вниз или снизу вверх. Речь идет о том, чтобы сосредоточиться на «чем» проблемы, а не на «как». Когда я начал с функционального программирования, я обнаружил, что продолжаю вспоминать императивные конструкции, такие как вложенный цикл for в C. Затем я быстро обнаружил, что попытка перевести свое императивное мышление в функциональные конструкции было очень трудным. Я постараюсь привести вам более конкретный пример. Я реализую эквивалентную программу на C и Haskell и попытаюсь отследить мой мыслительный процесс в обоих случаях. Обратите внимание, что я был явно многословен с целью объяснения.

В С:

#include <stdio.h>

int main(void)
{
  int i, inputNumber, primeFlag = 1;
  scanf("%d", &inputNumber);
  for(i = 2; i <= inputNumber / 2; i ++)
    {
      if (inputNumber % i == 0)
        {
          primeFlag = 0;
          break;
        }
    }
  if (primeFlag == 0) printf("False\n");
  else printf ("True\n");
  return 0;
}

След моего мыслительного процесса:

1. Думай поэтапно. Сначала примите номер от пользователя. Пусть это число будет называться inputNumber. scanf () записано.
2. Основной алгоритм: число является простым, если не доказано иное. primeFlag объявлено и установлено равным 1.
3. Проверьте primeNumber против каждого числа от 2 до primeNumber/2. for цикл начался. Объявлена ​​переменная цикла i для проверки primeNumber против.
4. Чтобы опровергнуть наше первоначальное утверждение о том, что число простое, отметьте primeNumber против каждого i. В тот момент, когда мы находим хотя бы одну i, которая делит primeNumber, установите primeFlag на 0 и break. Тело петли написано.
5. После прохождения нашего строгого процесса проверки в цикле for проверьте значение primeFlag и сообщите его пользователю. printf () написано.

В Хаскеле:

assertPrime :: (Integral a) => a -> Bool
assertPrime x = null divisors
    where divisors = takeWhile (<= div x 2) [y | y <- [2..], mod x y == 0]

След моего мыслительного процесса:

1. Число является простым, если у него нет делителей, кроме одного и самого себя. Итак, null divisors.
2. Как мы строим divisors? Во-первых, давайте запишем список возможных кандидатов. Записал Техасский диапазон от 2 до числа / 2.
3. Теперь отфильтруйте список и выберите только те элементы, которые действительно являются делителями числа. Написал фильтр mod x y == 0

Я хочу получить совет о том, как «мысли на функциональном языке»

Хорошо, прежде всего, подумайте «что», а не «как». Это может занять много практики, чтобы привыкнуть. Кроме того, если вы раньше были программистом на C / C ++, как я, перестаньте беспокоиться о памяти! Современные языки имеют сборщик мусора, и он написан для вас, так что даже не пытайтесь модифицировать переменные на месте. Еще одна вещь, которая мне лично помогла: запишите в своей программе английские определения, чтобы абстрагироваться от функций, которые выполняют тяжелую работу.

Answer 3

Через некоторое время я обнаружил, что функциональное программирование […] поощряет дизайн «сверху вниз».

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

• Сначала посмотрите на базовый вариант. Как вы сортируете массив из 0/1 элементов?
• Далее посмотрите на базу + 1, базу + 2,… кейсы. В конце концов вы должны увидеть шаблон (разбиение на подзадачи, решение подзадач, объединение подзадач), который позволяет вам написать общий рекурсивный случай, который в конечном итоге достигает базового случая.
• Разделить на подзадачи легко, но объединить подрешения немного сложнее. Вам нужен способ объединения двух отсортированных массивов в один отсортированный массив.
• Теперь соберите все вместе. Поздравляем, вы только что написали сортировку слиянием. :)

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

Answer 4

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

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

Answer 5

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

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

Через некоторое время я обнаружил, что функционал программирование […] поощряет вниз "дизайн.

Согласен.