Introduction
In our day to day lives we do Mathematical operations without any hassle and worry. Because we have all the tools we need like, numbers and the operators. Like 5 + 2 = 7, here we know that 5, 2, and 7 are numbers and what we are essentially doing is adding because of the operator +
.
Now, just imagine you don’t know what the numbers mean or their actual interpretation. You also don’t know the meaning of the +
symbol, but you still want to add two numbers. It's like a toddler trying to do this!
I welcome you to the world of TypeScript where you cannot do all these stuffs. TypeScript does understand numbers but doesn’t have the understanding of what numbers represent and how big they are, what exactly are mathematical operations.
So in this blogpost, I will be explaining you folks, how to do the exact same thing and try to make it more humane.
Prerequisites
Who is this blog post not for?
Let me tell you the hard truth upfront: this blog post is one of those rare cases where you might not need it. The purpose of this post is to understand the marvelous concepts used to implement such things in TypeScript.
I love TypeScript, and for fun, I am trying to dig into this!
What are we building?
In TypeScript you cannot do any arithmetic operation like the above 5+2
which is equal to 7. You can represent numbers in typescript like 5
or 2
but you cannot do anything with them.
In this blogpost we will be building typescript generic utilities that will help you to implement the arithmetic operations:
- Addition
- Subtraction
- Multiplication
- Division
After going through this blogpost, you will be able to achieve the following in TYPES!!!
type addResult = Add<5, 2> // 7
type subRes = Sub<50, 3>; // 47
type mulRes = Mul<2,10>; // 20
type divRes = Div<10, 2>; // 5
The Basics
Every good code that is implemented is based on a good foundation. In this section we will talk about the foundation of implementing the above generic utilities.
There are two main thing that we need to understand:
- Recursion
- And Tail Recursion
These concepts are really important and drive the entire thought process about these generic arithmetic utilities in TypeScript.
So let us start off by understanding recursion.
What is Recursion?
Recursion is the way through which you can perform certain action by calling the same action. In terms of real life example, recursion can look like this:
If you hold a mirror in front of a mirror then you see an endless mirror within mirrors.
In the similar way, recursion in programming is a way for a function to achieve the results by calling it self. To explain this further let me give you a classic yet simple example,
const sum1ToN = (num: number) => {
if(num === 0){
return 0;
}
return num + sum1ToN(num - 1)
}
This function will return the sum of all the numbers from 1 to N.
To give you guys a quick look let us see what happens from call stack perspective(I know this is a bit off the route but trust me this will help us understand the later section of the blogpost):
If you execute sum1ToN(4)
. This is what happens
4 + sum1ToN(3)
4 + 3 + sum1ToN(2)
4 + 3 + 2 + sum1ToN(1)
4 + 3 + 2 + 1 + sum1ToN(0) // <-------
4 + 3 + 2 + 1
4 + 3 + 3
4 + 6
10
In the call stack, numbers are unraveled until num = 0
. Once all numbers are spread out, reverse addition occurs, consuming more of the call stack. For example, when num
was 4, it took 8 stacks to finish. Imagine if num
is 100.
This unpacking method in recursion is inefficient because the last statement in sum1ToN
performs two operations: unpacking the number and calling the next number in recursion. The program must remember the previous steps.
But why study this? What does recursion have to do with efficiency?
Find out in the next section.
Limitations in TypeScript
All the arithmetic generic utilities that we are going to build involves heavy recursion to achieve the results. Next, the typescript has limitation on its call stack size. Following are the TypeScript limits of the call stack:
- If it is a normal statement in TS then recursion limit is 100.
- If it is inside a conditional statement then limit is below 1000.
Hence, if we go with the above normal recursion methods to implement our utilities then it would fill up these limits easily even with small numbers like 200 or so if the utilities are not implemented correctly.
The aim of our utilities would be that they should take inputs less 1000.
You can read more about these TS limits in this PR: https://github.com/microsoft/TypeScript/pull/45711
What is Tail Recursion?
There is a way out to this normal recursion technique where you can do these calculations efficiently by reducing the call stack sizes. This method is called as tail recursion. I am not going to go in-depth about tail recursion in this post but I will help you understand how it affects the call stack.
So tail recursion is a technique in which the last statement of the recursive function just calls the function it self and doesn’t do any further calculations combined with it.
For example, in the above sum1ToN
function the last statement num + sum1ToN(num -1)
should not be present in the tail recursion method according to its definition.
If we cannot do combined operation as the last call in our recursive function then how are we going to achieve results? Its simple, just make use of accumulator to remember the addition of the already visited numbers. Below is the quick look of tail recursion version of sum1ToN
:
const sum1ToN = (num: number, acc: number = 0) => {
if(num === 0)
return acc;
return sum1ToN(num - 1, acc + num);
}
Here, we introduce the second argument acc
to the function with a default value of 0
. This way, the program doesn’t need to remember previous calls. In our case, while unpacking the numbers in the call stack, we are also performing the calculations in the accumulator as shown below:
sum1ToN(3, 0 + 4)
sum1ToN(2, 0 + 4 + 3)
sum1ToN(1, 0 + 4 + 3 + 2)
sum1ToN(0, 0 + 4 + 3 + 2 + 1) // finally the acc is returned
See how the call stack got reduced!!! we don’t need to go through all the next steps of addition because we are doing addition while we are doing the unpacking of the numbers. Isn’t this great 🙂
💡 NOTE Even though this technique is efficient still at some point in our utilities we hit the above mentioned limits.
You can find out more about tail recursion in the below detailed and fantastic videos:
Let us dive into the implementation
In this section we will be implementing the following arithmetic utilities which look like below:
type Add<A extends number, B extends number> = [
...GetRange<A>,
...GetRange<B>,
]["length"];
type Sub<
A extends number,
B extends number,
Num1 extends Array<number> = GetRange<A>,
Num2 extends Array<number> = GetRange<B>,
> = Num2 extends [...Num1, ...infer R] // A < B; res = -ve
? `-${R["length"]}`
: Num1 extends [...Num2, ...infer T] // A > B; res = +ve
? T["length"]
: 0;
type Mul<
A extends number,
B extends number,
Counter = 0,
Acc extends Array<number> = [],
Num1 extends Array<number> = GetRange<A>,
> = B extends Counter
? Acc["length"]
: Mul<A, B, Inc<number & Counter>, [...Acc, ...Num1]>;
type Div<
N extends number,
D extends number,
Acc extends Array<number> = [],
ReducedN extends number = GetRange<N> extends [...GetRange<D>, ...infer T] ? T["length"] : 0,
> = N extends 0
? Acc['length']
: Div<ReducedN, D, [...Acc, 0]>;
I know these generic might look way difficult but trust me they are easy to understand. I will break down each and every part of these generic utilities so that you guys can grasp the concept behind it.
So without further ado, let us start by implementing our first utility Add
.
Add
In terms of arithmetic this is a no brainer, Add
utility will just add two numbers. There are couple of things that you need to understand before we start off with the implementation:
- We cannot do addition or any arithmetic operation of that sort. So to by-pass this we convert each input number into a tuple of numbers. For example, a number
4
will be represented as a tuple of four 0s i.e.[0, 0, 0, 0]
. - We will need an utility to generate tuples out of the input numbers
- Numbers greater than 1000 cannot be used because we might reach the TS stack limit discussed above.
So here is how our Add
utility will look like:
type Add<A extends number, B extends number> = [
...GetRange<A>,
...GetRange<B>,
]["length"];
Before we jump into the implementation, let us understand what the GetRange
utility is:
/**
* Generates a tuple of 0s for the specified number
*/
type GetRange<
N extends number,
Acc extends Array<number> = [],
> = Acc["length"] extends N ? Acc : GetRange<N, [0, ...Acc]>;
This utility will generate a tuple filled with 0s equal to number passed as input. So indeed it will do something like below:
type res = GetRange<4> // res = [0, 0, 0, 0]
The GetRange
utility works in the following manner:
- It takes input number for which the tuple range needs to be created which is
N
. - It also makes use of accumulator
Acc
which stores the actual range in each step of recursion. - Its a simple recursion where we check if the length of
Acc
equals to the numberN
then we stop the recursion and return theAcc
. - If not, we again call the
GetRange<N, [0, ...Acc]>
which passes updatedAcc
to theGetRange
with an addition of0
and the previous values ofAcc
by destructing it an array like this[0, ...Acc]
.
Taking a closer look at this utility, we can see that we are using the Tail recursion mechanism, since the last statement in the recursion is only the recursive call to the function and no other operation. And also we are making use of accumulator Acc
.
Now let us re-visit our Add
utility. In this utility we simple destructure the tuples from GetRange<A>
and GetRange<B>
inside an array. Finally we return the length of this array:
type Add<A extends number, B extends number> = [
...GetRange<A>,
...GetRange<B>,
]["length"];
type sum1 = Add<10, 5>; // 15
Subtract
Here is how the subtraction utility will look like in TypeScript:
/**
* Substracts two numbers
*/
type Sub<
A extends number,
B extends number,
Num1 extends Array<number> = GetRange<A>,
Num2 extends Array<number> = GetRange<B>,
> = Num2 extends [...Num1, ...infer R] // A < B; res = -ve
? `-${R["length"]}`
: Num1 extends [...Num2, ...infer T] // A > B; res = +ve
? T["length"]
: 0;
The output of this utility is either string when the output is a negative or a number when output is positive.
type subRes = Sub<50, 3>; // subRes = 47
type subRes = Sub<3, 50>; // subRes = "-47"
To understand this utility take a look at this flowchart:
Let us go through it step by step:
-
Sub
take 2 mandatory inputs which areA
andB
. It also has 2 default parametersNum1
andNum2
with the default value ofGetRange
's ofA
andB
. - Throughout the utility we make we make use of
Num1
andNum2
because it makes easier for comparison as we will see in the next steps. - It’s easier to compare the array’s with the help of variadic tuple feature of TypeScript. We first compare that if
B
is greater thanA
, if it is then our output would be negative i.e.A-B = -res
- We do that by comparing
Num2
tuple with an destructured tuple ofNum1
and a variadic elementR
. HereR
represents the left over 0s fromNum2
which in our case is the result. - If this is the case then we return a string
-R
's length. -
You can imagine this calculation in this way:
Sub<2,3, Num1=[0,0], Num2=[0,0,0]> // Inside Sub this is what happens when A < B: Sub<2,3, Num1=[0,0], Num2=[0,0,0]> = [0, 0, 0] extends [...[0,0], ...infer R] // Here R's value becomes [0] ? `-[0]['length']` // -1
Similarly if
A
is greater thanB
then the output will be positive and the result of the residue is stored inT
in this case which is a Tuple whose length we return as the output.
Multiplication
The Multiplication utility is a bit different than the Add
and Sub
. Here is how it looks like:
/**
* Multiplies two numbers
*/
type Mul<
A extends number,
B extends number,
Counter = 0,
Acc extends Array<number> = [],
Num1 extends Array<number> = GetRange<A>,
> = B extends Counter
? Acc["length"]
: Mul<A, B, Inc<number & Counter>, [...Acc, ...Num1]>;
This utility works on the following principle:
- Consider an example of
Mul<2,3>
, to generate an output of6
we should add number2
three times to get the value as6
. - So in this utility the first number, is the input that will be repeatedly added with itself
B
number of times which is our second input toMul
.
Here is what happens inside the utility:
- The utility takes 2 mandatory number based inputs
A
andB
. It takes 3 optional parametersCounter
Acc
andNum1
with it’s respective default values mentioned in the utility. - Since we are add
A
to itselfB
number of times therefore we need to check if we have actually done that or not. To do that we compareB
with theCounter
, if it matches then we return the length of theAcc
i.e. Accumulator which keeps track of this addition. - Or else we again call
Mul
withA
B
, with an incrementedCounter
with the help ofInc
utility and finally we pass a tuple with desctructure value ofAcc
andNum1
. - The last parameter to
Mul
in the recursive call is important because it stores the actual results. - The Incremented counter value is also important because it helps to stop the recursion.
- Here is how the
Inc
utility looks like, it is pretty straight forward hence not going to explain:
/**
* Utility to increment the number
*/
type Inc<N extends number> = [0, ...GetRange<N>]["length"];
Division
Similar to multiplication utility, in Division we try to reduce the numerator by denominator till the numerator becomes 0. While this is happening we maintain the count of no. of times numerator was reduced.
For this utility we are apply the following constraints:
- The numerator should be greater than the denominator.
- Numerator should be perfectly divisble by the denominator.
We are going to keep these constraints to our Div
utility because implementing use cases such as not divisble numbers, floating point numbers, negative numbers, recurring decimal digits etc makes the utility too complicated and is out of scope of this blog post.
Here is how the utility will look like:
/**
* Divides two numbers
*/
type Div<
N extends number,
D extends number,
Acc extends Array<number> = [],
ReducedN extends number = GetRange<N> extends [...GetRange<D>, ...infer T] ? T["length"] : 0,
> = N extends 0
? Acc['length']
: Div<ReducedN, D, [...Acc, 0]>;
Inside the utility following things happen:
- There are 2 mandatory inputs
N
andD
which stands for Numerator and Denominator. - Next, we have 2 optional inputs
Acc
andReducedN
with their respective default values. -
Acc
is the accumulator tuple that we use to keep a count of number of times we subtractedD
fromN
. -
ReducedN
has a default valueGetRange<N> extends [...GetRange<D>, ...infer T] ? T["length"] : 0
which compares theN
tuple with a tuple ofD
and a varidiac elementT
. This value is nothing but subtraction ofD
fromN
. You can refer to theSub
utility for this to understand the logic. - Next, inside the actual utility we check that if
N
has been exhausted completely i.e.N
is equal to 0. If it is then we return the length of theAcc
or else we again call theDiv
withReducedN
asN
, with sameD
as the denominator, and with an incrementedAcc
by appending0
to it.
Limitation
The purpose of these utilities is to understand different concepts and the power of typescript. Below are some of the uses cases that are purposely not implemented since it would overcomplicate stuff and would be out of scope of this blog post:
- For
Add
utility, we didn’t consider addition of negative numbers or combination of negative and positive numbers. This also leads to connectivity betweenSub
utility as well. This limitation also applies toMul
andDiv
- For all the utilities, operations related floating point numbers is not considered.
- Due to call stack limitation of TS we cannot do operations on numbers more than 999.
Summary
I know this blogpost isn’t going to be that fruitful in real life use cases but take a look at what are the things we learned from it today:
- We understood recursion and Tail recursion
- How does tail recursion helps in optimizing the code by reducing the call stack consumption.
- We saw how Typescript interprets numbers and also saw that we cannot do arithematic operations
- We learned Typescript’s limitation of its call stack size.
- We learned how we can interpret numbers in the form of tuple like
GetRange
andInc
. - Lastly, we saw how we can leverage the above technique to create
Add
Sub
Mul
andDiv
utilities.
So that’s all folks!. Hope you like my blog post.
Top comments (0)