Композиция функций - не является ли зацикливание на массиве несколько раз для нескольких операций неэффективным?

Question

Я пытаюсь понять концепции и основы функционального программирования. Я не собираюсь хардкор с Haskell или Clojure или Scala. Вместо этого я использую JavaScript.

Итак, если я правильно понял, идея функционального программирования состоит в том, чтобы создать программное приложение с использованием Pure Functions, которое заботится о том, чтобы обрабатывать единственную ответственность / функциональность в приложении. без каких-либо побочных эффектов.

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

I напишите 2 функции для удвоения и приращения соответственно, которые принимают целое число в качестве аргумента. Затем следует служебная функция, которая составляет функции, переданные в качестве аргументов.

{
    // doubles the input
    const double = x => x * 2

    // increments the input
    const increment = x => x + 1

    // composes the functions
    const compose = (...fns) => x => fns.reduceRight((x, f) => f(x), x)

    // input of interest
    const arr = [2,3,4,5,6]

    // composed function
    const doubleAndIncrement = compose(increment, double)

    // only doubled
    console.log(arr.map(double))

    // only incremented
    console.log(arr.map(increment))

    // double and increment
    console.log(arr.map(doubleAndIncrement))
}

Выводы следующие:

[4, 6, 8, 10, 12]  // double
[3, 4, 5, 6, 7]    // increment
[5, 7, 9, 11, 13]  // double and increment

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

Если массив увеличится в размере, не будет ли это неэффективным?

Используя al oop, это можно сделать в одном обходе с двумя операциями в одном l oop.

Как это можно предотвратить или моё понимание неверно каким-либо образом?

Answer 1

Это map, который пересекает массив, и это происходит только один раз. reduceRight перебирает список составных функций (2 в вашем примере) и пропускает текущее значение массива через эту цепочку функций. Эквивалентная неэффективная версия, которую вы описываете, будет:

const map = f => x => x.map(f)
const doubleAndIncrement = compose(map(increment), map(double))

// double and increment inefficient
console.log(doubleAndIncrement(arr))

Это показывает одну из l aws, которую map должна удовлетворять, что:

map(compose(g, f)) эквивалентен (isomorphi c) compose(map(g), map(f))

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

Answer 2

Оптимизация сложности времени при сохранении небольших и выделенных функций является широко обсуждаемой темой c в кадре.

Давайте рассмотрим следующий простой случай:

const double = n => 2 * n;
const square = n => n * n;
const increment = n => 1 + n;

const isOdd = n => n % 2;


const result = [1, 2, 3, 4, 5, 6, 7, 8]
  .map(double)
  .map(square)
  .map(increment)
  .filter(isOdd);
  
console.log('result', result);

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

мы могли бы решить эту проблему (промежуточные значения + ненужное количество операций), внедрив все операции (double, square, increment, isOdd) в единственная функция сокращения ... однако, это может привести к потере читабельности.

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

const double = n => 2 * n;
const square = n => n * n;
const increment = n => 1 + n;

const isOdd = n => n % 2;

const transducer = R.into(
  [], 
  R.compose(R.map(double), R.map(square), R.map(increment), R.filter(isOdd)),
);

const result = transducer([1, 2, 3, 4, 5, 6, 7, 8]);

console.log('result', result);

<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.26.1/ramda.js" integrity="sha256-xB25ljGZ7K2VXnq087unEnoVhvTosWWtqXB4tAtZmHU=" crossorigin="anonymous"></script>