Byte sized TypeScript #1 - Filter type
Tags: typescript, typelevel
Published: 2022-05-28 11:27:27

Hiya! Welcome to the first post of my new TypeScript blogpost series. 

In this series I'll demonstrate & deconstruct byte sized TypeScript snippets to help you understand how to write type-level code. 

---- 

Let's start shall we?


## Filter Type

In TypeScript we have a notion of tuple types which are basically directly comparable to Arrays in js. It looks something like this: 

```ts
type MyTuple = [1, 2, string, boolean, null];
```

Now let's say we want to implement a `Filter` method similar to JavaScript's native `Array.Filter` in Type Level, how do we do this? 

Here's the full implementation: 
As we go forward I'll explain this type line by line. 

```ts
type Filter<Arr extends unknown[], FilterBy> = Arr extends [
  infer FirstElement,
  ...infer Rest
]
  ? FirstElement extends FilterBy
    ? [FirstElement, ...Filter<Rest, FilterBy>]
    : Filter<Rest, FilterBy>
  : Arr;

type Demo = Filter<[1, 2, string, boolean], number>
// -> [1, 2]
```

[Open on playground](https://tsplay.dev/wXK3OW)

## Line 1: 

In line 1 we have `Arr extends [ infer FirstElement, ...infer Rest]`

In here we are saying: 
If `Arr` is equal to `[infer FirstElement, ...infer Rest]` then go into the true branch of the conditional type. This line will also ensure that the passed `Arr` is actually a Tuple. If not, the false branch will be taken which is returning the `Arr` in the last line.  

The important part is the `infer` keyword, infer keyword is the inspection glass of TypeScript, it can extract what the value of the type is at a particular place.   
Basically we are asking the TypeScript compiler "Hey! whatever is in this place assign it to this variable called `FirstElement`" 

Then we can access this `FirstElement` type's value in the conditional branch. 

Let's see an example: 

```ts
type GetFirstElementOfArray<Arr extends any[]> = 
  Arr extends [infer FirstElement, ...infer Rest] 
    ? FirstElement 
    : never

type Demo = GetFirstElementOfArray<[1, 2, 3]> // 1
```

You'll also notice the `...infer Rest` part, It is similar to JavaScript's rest syntax. This part will infer the rest of the elements in the array and save it in the variable called `Rest` which you can also access in the conditional branch, in this case it will have the values `[2, 3]`. 

## Line 5, 6, 7: 

Now we are inside the true branch of the conditional type 

![Screenshot of the Filter type with highlighted lines 5,6 & 7](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nv0rqq1txvfbp2aanoix.png)

At `FirstElement extends FilterBy` we are checking if the `FirstElement` is equal to `FilterBy`

If the above condition passes we are going to return a new tuple type `[FirstElement, ...Filter<Rest, FilterBy>]`, here we are including the `FirstElement` & then recursively calling the `Filter` generic again with the `Rest` of the elements. 

> Notice that we are also using the spread syntax `...Filter<Rest, FilterBy>`, since the Filter generic returns a tuple we can spread it's value in this new tuple we are returning. 

And if `FirstElement extends FilterBy` fails we are going to call the Filter recursively again but skipping the `FirstElement` this time, `Filter<Rest, FilterBy>`. 

Now let's step through the code on each recursive call to understand better what's happening: 

![Filter type step by step recursion states visualized](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4pcsyavdbwkj7pzjsrxc.png)
 

```ts
// Initial state
type D = Filter<[1, 'hello', 'world'], number>
```

Recursion #1:

```ts
// input <[1, 'hello', 'world'], number>
type Filter<Arr extends unknown[], FilterBy> = Arr extends [
  infer FirstElement, // 1
  ...infer Rest // ['hello', 'world']
]
  ? FirstElement extends FilterBy // 1 == number -> true
    ? [FirstElement, ...Filter<Rest, FilterBy>] // [1, ...Filter<['hello', 'world'], FilterBy>]
    : Filter<Rest, FilterBy>
  : Arr;

```

Recursion #2:

```ts
// input <['hello', 'world'], number>
type Filter<Arr extends unknown[], FilterBy> = Arr extends [
  infer FirstElement, // 'hello'
  ...infer Rest // ['world']
]
  ? FirstElement extends FilterBy // 'hello' == number -> false
    ? [FirstElement, ...Filter<Rest, FilterBy>]
    : Filter<Rest, FilterBy>  // Filter<['world'], FilterBy>
  : Arr;
```

Recursion #3:

```ts
// input <['world'], number>
type Filter<Arr extends unknown[], FilterBy> = Arr extends [
  infer FirstElement, // 'world'
  ...infer Rest // []
]
  ? FirstElement extends FilterBy // 'world' == number -> false
    ? [FirstElement, ...Filter<Rest, FilterBy>]
    : Filter<Rest, FilterBy>  // Filter<[], FilterBy>
  : Arr;
```

Recursion #4:

```ts
// input <[], number>
type Filter<Arr extends unknown[], FilterBy> = Arr extends [
  infer FirstElement, // unknown
  ...infer Rest // unknown
]
  ? FirstElement extends FilterBy
    ? [FirstElement, ...Filter<Rest, FilterBy>]
    : Filter<Rest, FilterBy>
  : Arr;
  // ^ false branch is taken since `Arr extends [infer FirstElement, ...infer Rest]` failed,
 //   thus empty Arr is returned.
```
 
That's about it, I hope you understood how the Filter type works now. At it's core the type is simple enough but understanding how each piece works is the important part. 

In case you still couldn't understand the type level code, how about we rewrite the type level code to runtime javascript code? 

You'll be surprised how similar it looks: 

```js
function Filter(Arr, FilterBy) {
    if (Arr.length < 1) return Arr;
    const [FirstElement, ...Rest] = Arr;
    if (typeof FirstElement === FilterBy) {
        return [FirstElement, ...Filter(Rest, FilterBy)];
    } else {
        return Filter(Rest, FilterBy)
    }
}

Filter([1, 2, 3, 'hello', true], 'number')
// [1, 2, 3]
``` 

Cool isn't it?

Anyways I think that's about it, I hope you learned something new & enjoyed the post. 

I'll be continuing this blogpost series, so make sure to follow me on [twitter](https://twitter.com/anuraghazru) or dev.to to get updated.