vial0ft

Posted on Jul 15, 2023

Pattern matching meets JS

#javascript #patternmatching #functional

sorta... kinda...

A few words about ...

Pattern matching is an extremely convenient concise mechanism for predominantly (until recently) programming languages (PL) that claim to be functional like Scala, Haskell, OCaml, Erlang (where this is generally one of the "language-forming" mechanisms), CLisp, etc. But some time ago, it began to appear in other PL's in one form or another.

What problem does pattern matching solve in a program? Let's look at an example from Scala:

def constantsPatternMatching(constant: Any): String = {
  constant match {
    case 0 => "I'm equal to zero"
    case 4.5d => "I'm a double"
    case false => "I'm the contrary of true"
    case _ => s"I'm unknown and equal to $constant"
  }
}

It is easy to see that the function executes one or another logical branch depending on what constant matches. In other words: pattern matching provides branching of execution logic. Almost like if or switch known in many PL's, especially C-like ones. However, it is important to note that in most implementations in different PL's, pattern matching is an expression and returns the result of executing logic from one of the branches. In the example shown above, the result of the match will be one of the four strings.

Of course, this example can be rewritten in any (or almost any) PL without using pattern matching with if or switch:

def constantsPatternMatching(constant: Any): String = {  
  if (constant.isInstanceOf[Int] && constant == 0) {  
    return "I'm equal to zero"  
  } else if (constant.isInstanceOf[Double] && constant == 4.5d) {  
    return "I'm a double"  
  } else if (constant.isInstanceOf[Boolean] && constant == false) {  
    return "I'm the contrary of true"  
  } else {  
    return "I'm unknown and equal to" + constant  
  }  
}

Note how much more cumbersome the construction is compared to the version with pattern matching. And the more complex checks are laid down for branching conditions and the more quantitatively the conditions, the more obvious the difference will be.

What is this note about?

Pattern matching looks very attractive for problem solving, and it's usually implemented at the PL level. However, JavaScript (JS) doesn't have this mechanism at the native (at least at the time of this writing).
In this note, the author has made an attempt to implement some kind of pattern matching mechanism using the constructs available in the language, because ... why not?

At the end of the note, there'll be links to other implementations of the pattern matching mechanism in JS from other authors.

Look and implementation

Before starting, the author'd like to leave a short disclaimer that the look or form that the user is supposed to interact with, as well as the implementation of the pattern matching aren't the only correct one. The author used those forms and available mechanisms of the language that he found convenient for demonstrating the idea.

Start to start

Groups to match

The author identified 3 groups of entities in JS that could be used in pattern matching:

primitives (undefined, boolean, number, bigint, string, symbol), their wrappers (String, BigInt, Symbol, Number, Boolean ) and null
arrays ([1,2,3,4,5])
associative arrays({a:1; b:2; c:3}) and custom class objects (new SomeClass())

User interface

Let's describe 3 functions and 2 constants, for using pattern matching by the user:
Functions:

a function that takes as arguments: the pattern to match against, guards (additional conditions for matching) and a function with logic to be executed if a match occurs. Since case is a keyword in JS, the function will be called ca$e =). The result of the ca$e function will be the function with logic, if the match is successful.
the match function, which takes as arguments a "pattern" and a sequence of ca$e function results. The result will either be the result of applying one of the resulting ca$e functions, or an exception will be thrown if none of the patterns matched
the default processing function el$e, this function is passed last, it is always true when matched and will be executed if none of the previous matches - it should be used to avoid an exception. Constants:
ANY - it is used as a wildcard value - i.e. no matter what will be in its place in the compared entity.
TAIL is a constant similar to ANY and it needs for arrays. It's used as wildcard of tail sequence.

How it should look like in the end

let result = 
  match(matchable)(
    ca$e(null)(_ => "null"),
    ca$e(2)(n => `${n} + 2 == 4`),
    ca$e([1, 2, ANY, 4, TAIL], (arr => arr.lehth > 10))(arr => "long array"),
    el$e(elseCase => `matching not found for ${elseCase}`)
)

The author would like to remind you that the appearance is determined solely by the preferences of the author and may be different - this will not greatly affect the logic.

Let's take a closer look at the appearance of the functions used:

match(some_value)(...ca$es) 

ca$e(pattern, ...guards)(success_match_function) 

el$e(matching_fallback_function)

The combination rules are as follows:

match wraps some_value using partial application and then applies it to each ca$e in turn. match can check any number of ca$e functions.
ca$e takes as its first argument a pattern to match, and the following arguments are treated as guards. ca$e closes them and waits for a function to be applied if the match succeeds.
el$e does not assume any matching logic and simply accepts a function that will be applied to the matched entity if none of ca$e is successful. el$e can be conditionally represented as ca$e(ANY)(matching_fallback_function)

To implementation...

ANY

ANY should be simple enough to use, yet contain a value that is hardly to be seen outside. For example, like this:

const ANY = "🍵_there's_could_be_any_value_what_you_can_imagine_🍵"

Agree - you hardly expect to meet a cup of tea in real code?

TAIL

Similarly with ANY:

const TAIL="🍵_there's_tail_of_array_just_don't_care_what's_could_be_🍵"

match

The match function must first accept an item for further matching, and then, to accept a sequence of ca$e functions, match returns a function as a result in which the main logic will be executed:

function match(item) {
  function match_cases(item, [head_case_func, ...tail_case_funcs]) {
    if (head_case_func == undefined) return null
    return head_case_func(item) || match_cases(item, tail_case_funcs)
  }

  return (...cases) => {
    const result_f = match_cases(item, cases)
    if (result_f != null) return result_f(matchable)
    throw Error("Match ERROR!!!");
  }
}

Here match_cases is a helper function that recursively applies item to the functions passed to ca$e until the first one returns null or until the sequence of ca$e functions is empty.
Note that item matching will not start until ca$e is passed to the function.

case ... sorry ca$e

First, let's define the arguments and return values of the ca$e function in general:

function ca$e(case_pattern, ...guards) {
  return (case_func) => (matchable) => {
      // **magic**
      return null            
    }
}

This view matches the pattern described above ca$e(pattern, ...guards)(success_match_function). The last return function is needed to run the matching logic. matchable will be passed to the match function when calling head_case_func.
Now let's start implementing the magic part.
We have a pattern to match (case_pattern) and we have something to match against. Let's do a simple check - what if they are strictly equal? And then we don't have to do anything - just check the guards conditions and return case_func as the result, i.e. matching was successful.

Equality

Let's write some helper functions:

function areTheyStrictEqual(matchable, case_pattern) {
  return matchable === case_pattern
}

function checkGuards(guards, matchable) {
  return guards.every(g => g(matchable))
}

And add this logic:

function ca$e(case_pattern, ...guards) {
  return (case_func) => (matchable) => {
    if((areTheyStrictEqual(matchable, case_pattern) ||
         case_pattern === ANY) &&
        checkGuards(guards, matchable)) {
        return case_func
      }
      // **rest part of magic**
      return null            
     }
}

It is also necessary to take into account the case when ANY is passed as a pattern

It can already to check the work with simple values:

let result = match(1)(
            ca$e(1)(one => `It's work! One!!! ${one}`)
         )
console.log(result) // It's work! One!!! 1

If we pass something that doesn't match the pattern, we'll get an exception:

let result = match(2)(
         ca$e(1)(one => `It's work! One!!! ${one}`)
         )
// Error: Match ERROR!!!
console.log(result)

While everything is expected. Let's continue...

Arrays

Let's write the logic for matching arrays. The match will be successful if the same array elements are in the same order. But first we need to figure out that matchable is an array. Let's write a helper function areEveryArray and then reduce the amount of magic a bit:

function areEveryArray(...maybeArrays) {
  return maybeArrays.length > 0 &&
         maybeArrays.every(Array.isArray)
}


function ca$e(case_pattern, ...guards) {
  return (case_func) => (matchable) => {
     if((areTheyStrictEqual(matchable, case_pattern) ||
         case_pattern === ANY) &&
       checkGuards(guards, matchable)) {
       return case_func
     }
     if(areEveryArray(matchable, case_pattern) &&
        checkArraysRec(matchable, case_pattern) &&
        checkGuards(guards, matchable)) {
        return case_func
      }
      // **rest part of magic**
      return null            
    }
}

checkArraysRec - this is the function that will deal with matching of arrays only:

function checkArraysRec(matchable_array , case_pattern_array) {
    if([matchable_array, case_pattern_array].every(a => a.length == 0)) return true //(1)
    let [head_m, ...tail_m ] = matchable_array
    let [head_cp, ...tail_cp] = case_pattern_array
    if(head_cp === TAIL) return true //(2)
    if(head_cp != ANY && !areTheyStrictEqual(head_m, head_cp)) return false //(3)
    return checkArraysRec(tail_m, tail_cp) //(4)
}

Let's go through the conditions:

If both arrays are empty: the matching is complete and no discrepancies were found, true is returned. Otherwise, we continue the matching.
If the pattern to match is the TAIL constant: no further comparison is important - return true. Otherwise, we continue the comparison.
If the pattern to match is not ANY and is not equal to the matched value (for now, leave this simple condition): a discrepancy is found and there is no point in continuing the match - false is returned
If none of the previous conditions is met, we continue the comparison.

Let's check:

match([1,2,3])(
  ca$e([2,2,3])(arr => `miss`),
  ca$e([1,2,3])(arr => `[1,2,3] == [${arr}]`)
)
// [1,2,3] == [1,2,3]

match([1,2,3])(
  ca$e([ANY,2,3], (([first, ...tail]) => first < 5))(arr => `first is small`),
  ca$e([1,2,3])(arr => `[1,2,3] == [${arr}]`)
)

// first is small

match([1,2,3])(
  ca$e([1, TAIL], (arr => arr.length < 5))(arr => `lenght is less than 5`),
  ca$e([ANY,2,3], (([first, ...tail]) => firts < 5))(arr => `first is small`),
  ca$e([1,2,3])(arr => `[1,2,3] == [${arr}]`)
)
// lenght is less than 5

Looks good. Next, we implement the logic for matching primitive types.

Primitives

Recall what primitive types are in JS, as well as about their wrapper classes:

Тип	Результат `typeof` от переменной	Обёртка
Null	`"object"`(why)	N/A
Undefined	`"undefined"`	N/A
Boolean	`"boolean"`	`Boolean`
Number	`"number"`	`Number`
BigInt	`"bigint"`	`BigInt`
String	`"string"`	`String`
Symbol	`"symbol"`	`Symbol`

Thus, to determine that we have a primitive in front of us, we need to check: that the typeof of the variable is one of the listed values in the second column from the table, or that the instanceof of the variable is one of the values from the third column.

const PRIMITIVE_AND_WRAPPER = {
  "boolean" : Boolean,
  "number" : Number,
  "bigint" : BigInt,
  "string" : String,
  "symbol" : Symbol
}

function isPrimitive(item) {
    return item === null || 
            ["undefined", ...Object.keys(PRIMITIVE_AND_WRAPPER)]
            .includes(typeof item) 
}

function isPrimitiveWrapper(item) {
    return Object.values(PRIMITIVE_AND_WRAPPER)
            .some(w => item instanceof w)
}

PRIMITIVE_AND_WRAPPER will be needed later

And combine these functions:

function areEveryPrimitive(...maybePrimitives) {
  return maybePrimitives.length > 0 && 
         maybePrimitives
         .every(e => isPrimitive(e) || isPrimitiveWrapper(e))
}

Let's add this logic to the ca$e function:

function ca$e(case_pattern, ...guards) {
  return (case_func) => (matchable) => {
    if((areTheyStrictEqual(matchable, case_pattern) ||
         case_pattern === ANY) &&
       checkGuards(guards, matchable)) {
       return case_func
    }
    if(areEveryArray(matchable, case_pattern) &&
       checkArraysRec(matchable, case_pattern) &&
       checkGuards(guards, matchable)) {
       return case_func
    }
    if(areEveryPrimitive(matchable, case_pattern) &&
       checkPrimitives(matchable, case_pattern) &&
       checkGuards(guards, matchable)) {
       return case_func
    }
    // **rest part of magic**
    return null
  }
}

checkPrimitives, like checkArraysRec, directly compares two values. But before implementing it, you need to write a few helper functions:

function sameTypes(matchable, case_value) {
    return typeof matchable === typeof case_value
}

function sameWrapperTypes(matchable, case_pattern) {
    return Object.values(PRIMITIVE_AND_WRAPPER)
            .some(w => matchable instanceof w &&
                  case_pattern instanceof w)
}

function arePrimitiveAndWrapperOrViceVersa(matchable, case_pattern) {
    return Object.entries(PRIMITIVE_AND_WRAPPER)
            .some(([pr, wrap]) =>
              (typeof matchable === pr && 
              case_pattern instanceof wrap) ||
              (typeof case_pattern === pr && 
                matchable instanceof wrap))
}

function areMatchableTypes(matchable, case_pattern) {
  return [sameTypes, 
          sameWrapperTypes, 
          arePrimitiveAndWrapperOrViceVersa]
          .some(f => f(matchable, case_pattern))
}

In areMatchableTypes, we consider primitives to be matched if one of the following conditions is true:

their types are equal. sameTypes
their wrappers are equal. sameWrapperTypes
the type of the value being matched is associated with the pattern value wrapper, or vice versa. arePrimitiveAndWrapperOrViceVersa

Now let's write the implementation of checkPrimitives:

function checkPrimitives(matchable, case_pattern) {
  if (case_pattern == ANY || areTheyStrictEqual(matchable, case_pattern)) return true
return areMatchableTypes(matchable, case_pattern) &&
        areTheyStrictEqual(matchable.toString(), case_pattern.toString())
}

It seems that everything looks quite simple here, except for the last line:

areTheyStrictEqual(matchable.toString(), case_pattern.toString())

Looking at it, someone may have a question "Why?". Why compare the string representation of primitives, especially considering that a little higher there was already a check of the values themselves?
Well... this is due to the special type system and their comparison in JS:

Symbol(1) === Symbol(1) // false
// But
Symbol(1).toString() === Symbol(1).toString() // true

Of course, if this case is not interesting, you can remove the comparison string representations at the end of the function.

Let's check:

match(1)(
    ca$e([1, TAIL], (arr => arr.length < 5))(arr => `lenght is less than 5`),
    ca$e("1")(_ => `It's number one but as string`),
    ca$e(new Number(1))(num_one => `It's number one`),
    ca$e(ANY)(any => `It something different`)
)
// `It's number one`

So far so good

Now in the array check we can change the check condition to a more correct one:

function checkArraysRec(matchable_array , case_pattern_array) {
  if([matchable_array, case_pattern_array].every(a => a.length == 0)) return true //(1)
    let [head_m, ...tail_m ] = matchable_array
    let [head_cp, ...tail_cp] = case_pattern_array
    if(head_cp === TAIL) return true //(2)
   // if(head_cp != ANY && !areTheyStrictEqual(head_m, head_cp)) return false //(3)
    if(!checkPrimitives(head_m, head_cp)) return false
    return checkArraysRec(tail_m, tail_cp) //(4)
}

Associative arrays and user-defined types

How to determine if a variable is an associative array or an instance of a custom class? We can say that if a variable does not refer to either primitives or arrays (Array), then it is an associative array or an instance of a custom class. It sounds logical, doesn't it?

function areEveryComplexStruct(...maybeComplexStruct){
    return maybeComplexStruct.length > 0 &&
            maybeComplexStruct
            .every(i => !(areEveryPrimitive(i) || areEveryArray(i)))
}

Let's also add a helper function to check if the classes match:

function sameCustomClass(matchable, case_pattern) {
    return matchable.constructor.name === case_pattern.constructor.name
}

Let's add a check to the ca$e function and remove the rest of the magic from there:

function ca$e(case_pattern, ...guards) {
  return (case_func) => (matchable) => {
    if((areTheyStrictEqual(matchable, case_pattern) ||
         case_pattern === ANY) &&
       checkGuards(guards, matchable)) {
       return case_func
    }
    if(areEveryArray(matchable, case_pattern) &&
       checkArraysRec(matchable, case_pattern) &&
       checkGuards(guards, matchable)) {
       return case_func
    }
    if(areEveryPrimitive(matchable, case_pattern) &&
       checkPrimitives(matchable, case_pattern) &&
       checkGuards(guards, matchable)) {
       return case_func
    }          
    if(areEveryComplexStruct(matchable, case_pattern) &&
       checkComplex(matchable, case_pattern) &&
       checkGuards(guards, matchable)) {
       return case_func
    }
    return null            
  }
}

checkComplex will be similar in concept to checkArraysRec:


function checkComplexRec(matchable, [kv_case_pattern, ...tail_case_pattern]) {
    if(kv_case_pattern == undefined) return true
    let [key_case_pattern, value_case_pattern] = kv_case_pattern
    let matchable_value = matchable[key_case_pattern]
    if(!checkPrimitives(matchable_value, value_case_pattern)) return false
    return checkComplex(matchable, tail_case_pattern)
}

function checkComplex(matchable, case_pattern_complex) {
    if(!sameComplexClass(matchable, case_pattern_complex)) return false
    return checkComplexRec(matchable, Object.entries(case_pattern_complex))
}

Let's check the solution:

match({x:1, y:2})(
    ca$e([1, TAIL], (a => a.length < 5))(a => `lenght is less than 5`),
    ca$e("1")(_ => `It's number one but as string`),
    ca$e(new Number(1))(num_one => `It's number one`),
    ca$e({x:1, y:2, z: 3})(obj => "xyz"),
    ca$e({x:1, y:2})(obj => "It's complex object"),
    ca$e(ANY)(any => `It something different`)
)
// It's complex object

match({x:1, y:2})(
    ca$e([1, TAIL], (a => a.length < 5))(a => `lenght is less than 5`),
    ca$e("1")(_ => `It's number one but as string`),
    ca$e(new Number(1))(num_one => `It's number one`),
    ca$e({x:1, y:2, z: 3})(obj => "xyz"),
    ca$e({x:ANY, y:2})(obj => "It's complex object and x is ANY"),
    ca$e(ANY)(any => `It something different`)
)
// "It's complex object and x is ANY"

class A {
  constructor(a) {
    this.a = a
  }
}

class B {
  constructor(a) {
    this.a = a
  }
}

match(new A(42))(
  ca$e([1, TAIL], (a => a.length < 5))(a => `lenght is less than 5`),
    ca$e("1")(_ => `It's number one but as string`),
    ca$e(new Number(1))(num_one => `It's number one`),
    ca$e({x:1, y:2, z: 3})(obj => "xyz"),
    ca$e({x:1, y:2})(obj => "It's complex object"),
    ca$e(new B(42))(cls => "Mehhh..."),
    ca$e(new A(42))(cls => "wow such custom class wow 🐶"),
    ca$e(ANY)(any => `It something different`)
)

// "wow such custom class wow 🐶"

👍

Just one more thing...

.... which lies in the fact that an array, an associative array or a custom class could contain not only primitives, but also arrays, associative arrays or instances of custom classes can also be used as values. In this case, checking

if(!checkPrimitives(matchable_value, value_case_pattern)) return false

will stop working. Let's fix this and write a function that decides what kind of instance we have and what to do with it:

function chooseCheckFunction(matchable, case_pattern) {
    if(areEveryArray(matchable, case_pattern)) return checkArraysRec
    if(areEveryComplexStruct(matchable, case_pattern)) return checkComplex
    if(areEveryPrimitive(matchable, case_pattern)) return checkPrimitives
    return null;
}

And let's apply it
For arrays:

function checkArraysRec(matchable_array , case_pattern_array) {
    if([matchable_array, case_pattern_array].every(a => a.length == 0)) return true
    let [head_m, ...tail_m ] = matchable_array
    let [head_cp, ...tail_cp] = case_pattern_array
    if(head_cp === TAIL) return true
    //  if(!checkPrimitives(head_m, head_cp)) return false
    //  return checkArraysRec(tail_m, tail_cp)
    if(head_cp === ANY) return checkArraysRec(tail_m, tail_cp)
    let check_func = chooseCheckFunction(head_m, head_cp)
    return check_func && check_func(head_m, head_cp) &&
         checkArraysRec(tail_m, tail_cp)
}

For "complex" entities:

function checkComplexRec(matchable, [kv_case_pattern, ...tail_case_pattern]) {
    if(kv_case_pattern == undefined) return true
    let [key_case_pattern, value_case_pattern] = kv_case_pattern
    let matchable_value = matchable[key_case_pattern]
    //if(!checkPrimitives(matchable_value, value_case_pattern)) return false
    //return checkComplex(matchable, tail_case_pattern)
    if(value_case_pattern === ANY) return checkComplexRec(matchable, tail_case_pattern)
    let check_func = chooseCheckFunction(matchable_value, value_case_pattern)
    return check_func && check_func(matchable_value, value_case_pattern) &&
         checkComplexRec(matchable, tail_case_pattern)
}

Let's check that the matching works with nested entities:

match({x:1,y: {z: 2}})(
    ca$e({x:1, y:2, z: 3})(obj => "xyz"),
    ca$e({x:1, y: {z: 2}})(obj => "It's very complex object"),
    ca$e(ANY)(any => `It something different`)
)

// It's very complex object

You can verify the work of the previous examples, as well as cases with composition of arrays, associative arrays, and user-defined classes for yourself.

el$e

The el$e alternate action function, that fires when none of the ca$e functions have worked, is quite simple - all it has to do is follow the sequence of return functions by analogy with ca$e:

function el$e(f) {
  return () => (matchable) => f(matchable)
}

More better

The last change the author would like to make is to replace some of the logic inside ca$e using the new selection function of checking:

function ca$e(case_pattern, ...guards) {
    return (case_func) => (matchable) => {
      if(areTheyStrictEqual(matchable, case_pattern) && 
         checkGuards(guards, matchable)){
         return case_func
      }
      // if(areEveryArray(matchable, case_pattern) &&
      //     checkArraysRec(matchable, case_pattern) &&
      //     checkGuards(guards, matchable)) {
      //     return case_func
      // }
      // if(areEveryPrimitive(matchable, case_pattern) &&
      //     checkPrimitives(matchable, case_pattern) &&
      //     checkGuards(guards, matchable)) {
      //     return case_func
      // }
      // if(areEveryComplexStruct(matchable, case_pattern) &&
      //     checkComplex(matchable, case_pattern) &&
      //     checkGuards(guards, matchable)) {
      //     return case_func
      // }
      let check_func = chooseCheckFunction(matchable, case_pattern)

      return check_func && 
             check_func(matchable, case_pattern) &&
             checkGuards(guards, matchable) ? case_func : null 
   }
}

That all folks!

The author hopes that you did not get bored and learned something new about JS.

DEV Community