Multiplication of large numbers in a functional programming style
A simple, at first glance, task — multiplying numbers, can cause a lot of problems if these numbers are large. I faced such task on Сodewars. In addition to the basic rules of multiplication, there were the following conditions:
- The arguments are passed as strings.
- The numbers may be way very large.
- Answer should be returned as a string.
- The returned “number” should not start with zeros e.g. 0123 is invalid.
There are several options for solving this problem. The most popular solution from yangzj1992. Taking it as a basis, I decided to write a solution in a functional programming style.
Monad and functions that will help solve this problem, I took from the book “Professor Frisby’s Mostly Adequate Guide to Functional Programming”. We need a monad “Either”.
Monad “Either” — it allows to build a logic on analogy with “if … else”. Also two classes that inherit the “Either” monad — “Left” and “Right”. We will apply the “Right” when the result of the condition suits us, and we can apply the next function in the chain to it. And “Left” when the result of the previous function in the chain does not fit the conditions. Then we just estimate the value further down the chain. The main condition for multiplication — if you multiply by zero, then there will be zero. Accordingly, we do not need to calculate something, if one of the factors is zero, you just need to return it. To do this, and need “Either”.
To assemble our functions in a chain, we need three classic functions from functional programming for currying and composition, as well as the functions “either” and “identity”.
Now we will write some well-known to us auxiliary functions for working with arrays.
// 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');
With the first three functions, everything is simple. And about the following, I will tell more in detail.
The “sliceByIndex” function is curried and will wait for the array and index to perform its calculations. Suppose a zero comes in instead of an array, then the function simply returns zero, thanks to the monad “Either”. The “findFirstNatureNumIndex” function looks for the index of the first natural number in the array.
Next, we compose these functions to get a number that does not start with zeros.
// 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)
The function “sliceFromIndex” will wait for two functions — “sliceByIndex” and “findFirstNatureNumIndex”, which is described above, as well as an array, in order to apply these functions to it. The function “compactNum” will transfer the first two arguments to the function “sliceFromIndex”. Then we pass it the array in the “getCompactNum” function, including it in the composition.
It is necessary to determine whether to use the function or not, depending on the conditions. This will help us three more functions that we include in the chain.
// 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 })
})
Almost come to an end. Now we need to get an array from string numbers. Let’s write the function “getArrFromStrNum”.
// getArrFromStrNum :: String -> [String]
const getArrFromStrNum = compose(
either(identity, getCompactNum), applyIfIsNotZero
);In this function, we pass a number, and if it is not zero, we get a compact array. The “getCompactNum” function gets an array of numbers, skipping zeros at the beginning of a number. We describe it below. Then the resulting arrays need to be multiplied together, getting one array at the output. The functions “multiplyArrays” and “getMultipliedArray” will help us in this.
// 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);
The function “getMultipliedArray” checks whether the arrays are at the input and if so, then multiply them with the help of the “multiplyArrays” function. The resulting array must be mapped so that the output will get a multiplied number. To do this, we write one more function.
// 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;
}
We map the array, forming a stack, in the cell of which only one digit should remain, tens and other orders are transferred to the position above in the stack. It now remains to compile this function with auxiliary functions and transfer the numbers as an array using the “getArrFromStrNum” function.
// getMultipliedNumber :: [String] -> string
const getMultipliedNumber = compose(join , reverse, either(identity, mapMultipliedArray), applyIfIsNotZero);const multiply = (a, b) => getMultipliedNumber(
getMultipliedArray(getArrFromStrNum(a), getArrFromStrNum(b))
);
All code can be viewed on Github.
P.S. I am sorry if my code style or Hindley Milner’s typing was not entirely correct. I will be glad to any constructive criticism and discussion. Thanks for attention!
