Совет относительно изучения, “Как думать функциональный”?

After a while, I found that functional programming [...] encourages a "top down" design.

Well, it's not about "top down" or "bottom up" design really. It's about focusing on the "what" of the problem at hand, rather than the "how". When I started off with functional programming, I found that I kept recalling imperative constructs like the nested for loop in C. Then I quickly found out that trying to translate my imperative thinking to functional constructs was very difficult. I'll try to give you a more concrete example. I'll implement an equivalent program in C and Haskell and attempt to trace my thought process in both cases. Note that I've been explicitly verbose for the purpose of explanation.

In C:

#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;
}

Trace of my thought process:

1. Think in steps. First, accept a number from the user. Let this number be called inputNumber. scanf() written.
2. Basic algorithm: A number is prime unless otherwise proven. primeFlag declared and set equal to 1.
3. Check primeNumber against every number from 2 to primeNumber/2. for loop started. Declared a loop variable i to check primeNumber against.
4. To disprove our initial assertion that the number is prime, check primeNumber against each i. The moment we find even one i that divides primeNumber, set primeFlag to 0 and break. Loop body written.
5. After going through our rigorous checking process in the for loop, check the value of primeFlag and report it to the user. printf() written.

In Haskell:

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

Trace of my thought process:

1. A number is prime if it has no divisors but one and itself. So, null divisors.
2. How do we build divisors? First, let's write down a list of possible candidates. Wrote down Texas range from 2 to number/2.
3. Now, filter the list, and pick out only items that are really divisors of the number. Wrote the filter mod x y == 0

I want to get advice about how to «думать функциональным языком»

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

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

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

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

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

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

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

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

Точно так же в некоторых изолированных племенах есть только одно слово для чисел больше 3 или нет слов для "мое" / "ваше". Такое ощущение, что в популярных языках нет слов для "

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

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

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

Согласен.