Pattern Matching in TypeScript: Tuples and Records

Intro

As mentioned in my previous article, while being on a vacation and work-free I decided to challenge myself with implementing pattern matching in TypeScript. While sitting in airports and planes and shuttles and between all the dancing workshops and social parties (I do social dancing and I highly recommend everyone to try it - I can draw so many parallels of social dancing and programming plus it's insanely fun) I was diving into my laptop to improve and add on the pattern matching project of mine.

In the first part, we discussed the basic patterns using OCaml, drew our conclusions and translated the generated ideas into TypeScript. In the end, we got to have basic patterns and a working POC. However, we missed two very major features - support of tuples and records (i.e. objects). In this article, I will talk about implementing those features on top of the code we already wrote.

Part 1: Implementing Tuples

In Functional Programming languages, what makes pattern matching insanely powerful is the fact that you can pattern match against the combination of several things at once. That is usually implemented using a data structure called tuples, which is a collection of items of different types. For example, a 3D coordinate could be represented as a tuple of 3 integers, a bingo cell can be represented as a tuple of a char/string and an integer, etc. Let's as always start from an OCaml example of the concept.

let match_tuple a b = 
    match a, b with
        1, 1 -> "Both  are one"
      | 1, _ -> "First is one"
      | _, 1 -> "Second is one"
      | _ -> "None is one"

a, b or (a, b) is a way to make a pair, i.e. tuple with two elements in OCaml. We later match the tuple value just like any other value, and the matched patterns are tuple patterns as well. Yet again, the matched tuple patterns can consist of other patterns as well. Let's see an example of using a tuple of list patterns to merge two sorted lists into one big sorted list.

let rec merge x y =
  match x, y with
    [], l -> l
  | l, [] -> l
  | hx::tx, hy::ty ->
     if hx < hy
     then hx :: merge tx (hy :: ty)
     else hy :: merge (hx :: tx) ty

It's a feast for the eyes to see a merge function written in such an elegant way, clearly talking about the algorithm without any technical overhead. So, let's try to bring this elegance to our implementation.

Design thoughts

First things first, we need to have some way to declare a tuple. If the TS sense, a Tuple is an array consisting of any number of Matchable values. However, we need some differentiation between a Tuple value and an ordinary array. This is mainly because we don't have mechanisms to determine if the given array is a Tuple or just an ordinary array during runtime. We do need these mechanisms for our matching algorithm.

After we are confident we have a way to differentiate the Tuples, we need to think about the matching process. As per usual, because the patterns can be consisting of other patterns, we need to set up a recursive mechanism of some sort. In the case of tuple patterns, we should call the match function with each element inside the tuple pattern and the corresponding tuple value, one by one. Consequently, the pattern match happens if and only if:

• Both the tuple pattern and the tuple value have the same amount of elements.

• All the constituting elements of the tuple pattern and tuple value are matching. If any of the tuple parts don't match, the whole tuple pattern doesn't match.

As the matching happens, we need a place to store and collect all the bindings that get created. Each constituting part of the matched tuple pattern and tuple value will create their bindings and we need to collect all of these in one place.

All the tuple-matching logic smells a lot like a reduce, because we need to go over all the given elements (aka parts of the tuple) and produce one resulting object (in this case a bindings array)

Implementation

We need to start by taking care of the types. Hence, let's create the special Tuple type we talked about above, and the function to produce Tuple values. Here is what our Tuple type will look like:

type TupleVal = {_valueType: 'tuple', _data: Matchable[]};

Of course, Tuple values are also Matchable values, so Matchable type should be updated accordingly.

type Matchable = number | string | boolean | Matchable[] | TupleVal;

We also need a pattern-creating function for Tuples, just like we had for all the other types of patterns.

// Tuple pattern's data field keeps a list of patterns
// which are the components of the given tuple pattern
// Hence the type of the Tuple Pattern is Pattern<Pattern[]>
const Tuple: (...args: Pattern[]) => Pattern<Pattern[]> 
  = (...args) => ({
      _patternType: 'TupleP',
      _data: args,
    })

And finally, we need a function to wrap values and produce tuple values.

const MakeTuple: (...args: Matchable[]) => Matchable = (...args) => {
  // Can't make a Tuple if there is just one value.
  if (args.length <= 1) {
    throw new Error('Tuple should have more than 1 arg');
  }

  return {
    _valueType: 'tuple',
    _data: args
  }
}

This function takes any number of Matchable values as arguments and saves them under a wrapper. The wrapper sets 2 private fields: _valueType is the type and is set as tuple and the data given is saved under the _data key.

With this already in place, we need to change the switch statement a bit and consequently the function of finding the value's type. Remind you that we use the switch against the typeof value statement. But now we have a tuple value that needs to be taken care of. So, let's write a function that will standardize the value type.

const determineValueAndType = (value: Matchable) => {
  if (typeof value === 'object' && !Array.isArray(value) 
    && value._valueType === 'tuple'
  ) {
    // Is for sure tuple 
    return value as TupleVal
  }

  return {
    _valueType: typeof value,
    _data: value
  }
}

We check the value to see if it's a Tuple, if so we don't need a wrapper around it. Otherwise, let's use the same wrapper signature for all the other types of values, just for consistency.

Now, the grand finale - let's adjust the main block of our matching - the matches function. The first minor thing to adjust is using the determineValueAndType function.

const matches: 
    (value: Matchable, pattern: Pattern) => Matchable[] | null 
  = (value, pattern) => {
  const { _data: data, _valueType: valueType } = 
    determineValueAndType(value);

  // ... The old code as is

  // Changing the switch statement.
  switch (valueType) {
    // The cases
  }
}

The last thing left is to add the case for the tuple:

const matches: 
    (value: Matchable, pattern: Pattern) => Matchable[] | null 
  = (value, pattern) => {
    // ...
    switch(valueType) {
      // ...
      case 'tuple':
        // Check if the pattern type is also tuple
        // The tuple pattern and the tuple value can 
        // only match if they have the same amount
        // of elements.
        if (patternType === 'TupleP' 
            && patternData.length === data.length
        ) {
          // Derive the list of bindings by matching 
          // individual components of the tuple.
          // acc is the list of final bindings and is
          // null if the pattern doesn't match the value
          return data.reduce((acc: Matchable[] | null, valueComponent, i) => {
            // Grab the pattern component corresponding to the
            // current value component using the index.
            const patternComponent = patternData[i];
            // If the matching haven't failed so far the list is 
            // still not null, so continue with the match.
            if (acc !== null)  {
              // Match the current components and determine the 
              // Bindings coming out of it.
              const newBindings = matches(valueComponent, patternComponent);
              // If the result of matching the components is successful
              if (newBindings !== null) {
                // Add the new bindings to the collection.
                return acc.concat(newBindings)
              }
            } 
            // If the pattern matching failed before, or
            // the matching of current value/pattern pair failed
            // set the bindings array to null and continue.
            return null;
          }, []);
        }
        return null;
    }
}

Congratulations! One more feature is available for use, it's time to commit and push. :)

Part 2: Implementing Records

Another powerful pattern-matching feature is the ability to match records, also known as objects.

(* We need to define the type before defining records *)
type person = { name : string; age : int; }
let me = {name="Rob"; age=24}
match me with
  {name="John"; age=_} -> "John"
  | {name=_; age=150} -> "Unknown ancient"
  | {name="Rob"; age=27} -> "Future Rob"
  | {name="Jess"; age=24} -> "Same age Jess"
  | {name="Rob"; age=24} -> "Rob"
  | _ -> "Someone else"

You can also use pattern matching to achieve destructuring like so:

(* Syntactic sugar for {name=name; age=age} *)
match me with
    {name; age} -> name

Additionally, the partial pattern matches the value:

match me with
    {name="Rob"} -> "It's me"
  | _ -> "It wasn't me"

With all this information at hand, we are equipped to think about the design.

Design Thoughts

Generally, as you can see, record pattern components can represent any pattern by themselves: the keys stay the same but the pattern that comes after the key name and the equal sign can be any pattern we already know about.

To put it more clearly let's summarize the rules of record pattern matching: For any value with fields {f1=v1, f2=v2, ..., fn = vn} the pattern {f1=p1, f2=p2, ..., fm=pm} matches if and only if

• The number of fields in the pattern is less than or equal to the number of fields in the value - m <= n

• For all fields in the pattern, the field names are also defined in the value - for any i for which pi is defined fi exists in the value.

• All the components of the record pattern match their corresponding values - for any i for which pi is defined, pi matches vi. All the matches can produce bindings.

Similarly to tuples, we need to aggregate all the bindings in one place and that would be the collection of bindings that the pattern matching of the record would create. As you may have guessed, we will use a reduce in a very similar fashion. The only difference would be converting the object at hand to an iterable. Luckily, we have built-in methods like Object.keys() and Object.values() to take care of that part.

Implementation

In a similar fashion to the work with the Tuples, let's first take care of the types. We have a new type of Matchable value. The new matchable value is an object, where the keys can be any string and the values should be matchable. That means that the new matchable value is of type Record<string, Matchable>.

type Matchable = number | string | boolean 
    | Matchable[] | TupleVal | Record<string, Matchable>;

But wait, this is invalid code, it shows an error and won't even compile. Well yes, that's true and if you want to know why it doesn't work, you can read TypeScript's lead architect's comment here. We will use the same logic to fix the issue:

interface MatchableRecord extends Record<string, Matchable> {};
type Matchable = number | string | boolean 
    | Matchable[] | TupleVal | MatchableRecord;

Great, now as this work let's also define the Record pattern. It will look very similar to almost all the other patterns:

const Record: (a: Record<string, Pattern>) => 
    Pattern<Record<string, Pattern>> = 
  (a) => ({
    _patternType: 'RecordP',
    _data: a,
  })

Finally, the only thing left is to update the matches function to handle the Records for us. The value type of object seems sufficient enough for us. The only issue is that typeof any array is also an object. So We will need to check if the value is an array or an ordinary object. We will do this using Array.isArray method.

// In the matches function
// switch (valueType) {
// ...
    case 'object':
      if (Array.isArray(data)) {
        // Handle the pattern matching of the array
      } else {
        if (patternType === 'RecordP') {
          // Pattern type seems right.
          const patternData = (pattern as 
                Pattern<Record<string, Pattern>>)._data || {};
          // Iterate over the keys of the pattern
          return Object.keys(patternData).reduce(
            (acc: Matchable[] | null, patternKey) => {
              // For every key in pattern, take the pattern
              // associated with it
              const patternComponent = patternData[patternKey];
              // And also for every pattern key, take the data
              // from the matched value
              const valueComponent = (data as MatchableRecord)[patternKey];
              // If the matching hasn't failed yet, and the 
              // matched value does have the property that's in 
              // the pattern
              if (acc !== null && data.hasOwnProperty(patternKey)) {
                // match the corresponding components
                const newBindings = 
                    matches(valueComponent, patternComponent);
                // If match was successful, add the generated bindings
                // to the list of the bindings.
                if (newBindings !== null) {
                  return acc.concat(newBindings);
                }
              }
              // If any condition from above failed, return
              // null to indicate a failed pattern match.
              return null;
            }, []
          );
        }
      }
      return null
// } 
// ...

That's it! Now we have a powerful pattern-matching tool that handles not only primitive data types and arrays. Our tool now can pattern match a collection of values at the same time utilizing the Tuple data structure and it can also pattern match objects of various kinds.

Conclusion

We learned about a new data structure called tuples and how we can use it to match multiple things at the same time. We saw challenges in the way regarding the types of things we use and how we can make them clearer for our usage. We then proceeded to integrate pattern matching of objects to our small program using several built-in JS features such as Object and Array methods.

The full code of the job done can be found here. If you have time, check my other work as well. If you have any suggestions or challenges on what to implement next - hit me up on any social media: I am currently trying to update my GitHub, for the last 2 years I used GitHub Enterprise and my personal GitHub went dead, so I am open to ideas.

Afterword

Implementing the pattern-matching tool was a highly recreational and challenging experience for me. It helped me strengthen my grasp of not only functional programming paradigms and core JavaScript concepts but also my understanding of TypeScript and its internals. Explaining it to an audience and typing it out helped me even more to clarify everything.

Projects like this always expose the knowledge of the things that we use without thinking about the "under the hood". Being able to code the tools and the features that a person uses for their day-to-day development tasks is what makes a developer stand out. So go ahead and challenge yourself with tasks like this from time to time and combine the useful with the pleasant.