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

  1. Аргументы передаются в виде строк.
  2. Цифры могут быть очень большими.
  3. Ответ должен быть возвращен в виде строки.
  4. Возвращаемое «число» не должно начинаться с нулей, например. 0123 недействителен.

Есть несколько вариантов решения этой проблемы. Самое популярное решение от yangzj1992. Взяв его за основу, я решил написать решение в стиле функционального программирования.

Монаду и функции, которые помогут решить эту проблему, я взял из книги Наиболее адекватное руководство профессора Фрисби по функциональному программированию. Нам нужна монада Либо.

Монада «Либо» - позволяет построить логику по аналогии с «если… иначе». Также два класса, наследующие монаду «Either» - «Left» и «Right». Мы применим «Правильно», когда результат условия нас устраивает, и мы сможем применить к нему следующую функцию в цепочке. И «Влево», когда результат предыдущей функции в цепочке не соответствует условиям. Затем мы просто оцениваем стоимость дальше по цепочке. Главное условие умножения - если умножить на ноль, то будет ноль. Соответственно, нам не нужно что-то рассчитывать, если один из коэффициентов равен нулю, нужно его просто вернуть. Для этого и понадобится «Либо».

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

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

// stringToArray :: String -> [String]
const stringToArray = (str) => str.split('');
// reverse :: [a] -> [b]
const reverse = (a) => [...a].reverse();
// join :: [a] -> String
const join = (a) => a.join('');
// sliceByIndex :: [a] -> [b]
const sliceByIndex = curry((a, i) => a.slice(i));
// findFirstNatureNumIndex :: [a] -> Number
const findFirstNatureNumIndex = (a) => a.findIndex(el => el !== '0');

С первыми тремя функциями все просто. А о следующем я расскажу подробнее.

Функция sliceByIndex каррирована и будет ждать, пока массив и индекс выполнят свои вычисления. Предположим, что вместо массива поступает ноль, тогда функция просто возвращает ноль благодаря монаде «Either». Функция findFirstNatureNumIndex ищет индекс первого натурального числа в массиве.

Затем мы составляем эти функции, чтобы получить число, не начинающееся с нулей.

// sliceFromIndex :: f -> fn -> [a] -> [a]
const sliceFromIndex = curry((f, fn, a) => compose(f(a), fn)(a));
// compactNum :: [a] -> [a]
const compactNum = sliceFromIndex(
  sliceByIndex, findFirstNatureNumIndex
);
// getCompactNum :: [a] -> [a]
const getCompactNum = compose(reverse, compactNum, stringToArray)

Функция sliceFromIndex будет ждать двух функций - sliceByIndex и findFirstNatureNumIndex, которые описаны выше, а также массива, чтобы применить к нему эти функции. Функция compactNum передаст первые два аргумента функции sliceFromIndex. Затем мы передаем ему массив в функции getCompactNum, включая его в состав.

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

// applyIfIsNotZero :: a -> Either(a, a)
const applyIfIsNotZero = curry((val) => (
 val !== '0' ? Either.of(val): left(val)
));
// applyIfIsArrays :: a -> b -> Either({a, b}, a)
const applyIfIsArrays = curry((arrA, arrB) => {
 if (arrA === '0') {
     return left(arrA)
   }
   if (arrB === '0') {
     return left(arrB)
   }
 return Either.of({ arrA, arrB })
})

Почти подошли к концу. Теперь нам нужно получить массив из строковых чисел. Напишем функцию getArrFromStrNum.

// getArrFromStrNum :: String -> [String]
const getArrFromStrNum = compose(
  either(identity, getCompactNum), applyIfIsNotZero
);

В этой функции мы передаем число, и если оно не равно нулю, мы получаем компактный массив. Функция getCompactNum получает массив чисел, пропуская нули в начале числа. Мы опишем это ниже. Затем полученные массивы нужно перемножить, получив на выходе один массив. В этом нам помогут функции multiplyArrays и getMultipliedArray.

// multiplyArrays :: {[a], [b]} -> [c]
const multiplyArrays = curry((arrA, arrB) => arrA.reduce(
(acc, elA, i) => {
 arrB.forEach((elB, j) => {
   const n = elA * elB;
    acc[i + j] = (acc[i + j]) ? acc[i + j] + n : n;
  })
  return acc;
}, []));
// getMultipliedArray :: ([a], [b]) -> Either([c], _)
const getMultipliedArray = compose(either(identity, multiplyArrays), applyIfIsArrays);

Функция getMultipliedArray проверяет, находятся ли массивы на входе, и если да, то умножает их с помощью функции multiplyArrays. Результирующий массив должен быть отображен так, чтобы на выходе было умноженное число. Для этого напишем еще одну функцию.

// mapMultipliedArray :: [Number] -> [Number]
const mapMultipliedArray = (arr) => {
 const stack = [...arr];
  for (var i = 0; i < stack.length; i++) {
    var num = stack[i] % 10;
    var move = Math.floor(stack[i] / 10);
    stack[i] = num;
    if (stack[i + 1])
      stack[i + 1] += move;
    else if (move != 0)
      stack[i + 1] = move;
  }
  return stack;
}

Сопоставляем массив, формируя стек, в ячейке которого должна остаться только одна цифра, десятки и другие порядки переносятся на позицию выше в стеке. Теперь осталось скомпилировать эту функцию с вспомогательными функциями и передать числа в виде массива с помощью функции «getArrFromStrNum».

// getMultipliedNumber :: [String] -> string
const getMultipliedNumber = compose(join , reverse, either(identity, mapMultipliedArray), applyIfIsNotZero);
const multiply = (a, b) => getMultipliedNumber(
getMultipliedArray(getArrFromStrNum(a), getArrFromStrNum(b))
);

Весь код можно посмотреть на Github.

P.S. Прошу прощения, если мой стиль кода или набор текста Хиндли Милнер был неправильным. Буду рад любой конструктивной критике и обсуждению. Спасибо за внимание!