Простая, на первый взгляд, задача - умножение чисел, может доставить массу проблем, если эти числа большие. С такой задачей я столкнулся на Сodewars. Помимо основных правил умножения, были следующие условия:
- Аргументы передаются в виде строк.
- Цифры могут быть очень большими.
- Ответ должен быть возвращен в виде строки.
- Возвращаемое «число» не должно начинаться с нулей, например. 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. Прошу прощения, если мой стиль кода или набор текста Хиндли Милнер был неправильным. Буду рад любой конструктивной критике и обсуждению. Спасибо за внимание!