0
$\begingroup$

How do different languages do pattern matching? In Rust it's

match x {
    y => ...,
    z => ...
}

However in ocaml it's

match x with
| y -> ...
| z -> ...

I'm wondering about some unique approaches to pattern matching.

$\endgroup$
1
  • 6
    $\begingroup$ The word "approaches" is vague; it could encompasses syntax, semantics and/or implementation details. The examples you've given are just different syntaxes and your question is tagged syntax, but the existing answers have mostly focused on semantics. I think the question would be improved if it asked specifically about semantics. $\endgroup$
    – kaya3
    May 23, 2023 at 9:57

4 Answers 4

4
$\begingroup$

Pattern matching syntax is somewhat uniform across languages. Sometimes you'll see if/else with single patterns, which may look like if let Some(x) = y {} (Rust), if(Some(var x) is y) {} (C#) or some variation of this.

Meanwhile,

Egison

Egison is a language that qualifies itself as Pattern-Match-Oriented.
An extensive SE answer would require to copy/paste Egi's entire thesis, so I'll try to summarise some interesting features.

def twinPrimes :=
    matchAll primes as list integer with
        | _ ++ $p :: #(p + 2) :: _ -> (p, p + 2)

take 6 twinPrimes
-- [(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)]

As you can see here, there exists a basic language that should be familiar (matchAll xs with <pattern> -> <expr>), however

  • Matching expressions may return one or multiple matches (match and matchAll, as do RegEx+),
  • Patterns may be self-referential ($p :: #(p + 2) matches 0, 2 but not 1, 2),
  • Matchers (the as list integer part above) are user-defined relations between the input and output.

This last point in particular allows to specify arbitrary matching strategies.
Here is an example of a pattern match ignoring the order of pairs:

def unorderedPair m :=
    matcher
        | ($, $) as (m, m) with
            | ($x, $y) -> [(x, y), (y, x)]
        | $ as (eq) with
            | $x -> [$x]

which can be used as

matchAll (2, 5) as unorderedPair with
    | (#5, $x) -> x

resulting in 2 due to the (#5, $x) branch attempting both possible order and succeeding with one.

Active Patterns

F#'s Active Patterns are a another pattern matching language where the matching logic is user-defined in functions with funky names like (|Even|Odd|), which may furthermore be parametrised.
In those names, essentially each possible branch is named after the bar-separated identifiers.

For example,

let (|Even|Odd|) n =
    if n % 2 = 0 then
        Even
    else
        Odd

do
    match 42 with
        | Even -> printfn "success"
        | Odd -> printfn "?"

Those functions being parametrisable allow to define arbitrary sublanguages, such as,

type MSpec<'a> =
    | Req of 'a
    | Opt of 'a

//xs is our parameter, ys is what we match against
let (|M|_|)<'a when 'a : equality> (xs: MSpec<'a> list) (ys: 'a list) =
    let rec f (xs': MSpec<'a> list) (ys': 'a list) =
        match xs' with
        | [] ->
            List.isEmpty ys'
        | (Opt xhd) :: xtl ->
            match ys' with
            | yhd :: ytl ->
                if xhd = yhd then
                    f xtl ytl
                else
                    f xtl ys'
            | _ ->
                f xtl ys'
        | (Req xhd) :: xtl ->
            match ys' with
            | yhd :: ytl -> 
                if xhd = yhd then
                    f xtl ytl
                else
                    false
            | _ ->
                false
    in
    if f xs ys then Some () else None
let g = function
| M [Opt 1; Req 2; Req 3] -> printfn "matches\n"
| _ -> printfn "nop\n"

do
    g [1; 2; 3] //matches
    g [2; 3]    //matches
    g [4; 2; 3] //nop

which should be reminiscent of RegExp's 1?23, and where a name with an underscore branch ((|M|_|)) uses Some/None.

$\endgroup$
3
$\begingroup$

Repurpose switch

This is what Swift does. From The Swift Programming Language:

let yetAnotherPoint = (1, -1)
switch yetAnotherPoint {
case let (x, y) where x == y:
    print("(\(x), \(y)) is on the line x == y")
case let (x, y) where x == -y:
    print("(\(x), \(y)) is on the line x == -y")
case let (x, y):
    print("(\(x), \(y)) is just some arbitrary point")
}
// Prints "(1, -1) is on the line x == -y"

In terms of the implementation, pattern matching calls the operator ~=.

However, Swift only lets you destructure tuples and enums, not structs. TSPL has a patterns chapter that lists all the valid patterns.

$\endgroup$
3
$\begingroup$

A unique pattern matching approach is the idris2/idris with rule.

The unique feature is that the item being matched is viewed as an added argument of the function, and when matching/destructing this "argument", the "existing/original arguments" can be affected as well. Here is an example function from the above documentation for converting a natural number to its binary representation (as a list of Bool's):

natToBin : Nat -> List Bool
natToBin Z = Nil
natToBin k with (parity k)
   natToBin (j + j)     | Even = False :: natToBin j
   natToBin (S (j + j)) | Odd  = True  :: natToBin j

where the parity of k (parity k) is matched (either Even or Odd). What's special is that depending on whether parity k is Even or Odd, the existing argument k is also refined/changed to j + j (when Even) or 1 + j + j (when Odd). This is different from most languages where you match a variable/expression by itself.

Additional details and definitions are in the documentation linked above.

$\endgroup$
1
$\begingroup$

Pattern matching in Papyri

Papyri is a dynamically-typed pure-functional programmable markup language which compiles to HTML. (Disclosure: I am the author of Papyri.)

The main things distinguishing Papyri from other languages are that the syntax is constrained to mostly be a superset of HTML, and HTML content (tags, text, and sequences) is a first-class data type, so the pattern-matching has to support it.

A pattern match expression in Papyri looks like this:

@match scrutinee {
    pattern1 -> branch1,
    pattern2 -> branch2,
    # ...
}

This is broadly similar to matching in other languages:

  • It's an expression so it results in a value and each branch must be an expression.
  • Patterns are in order of priority, so if more than one pattern could match then the earliest one is used.
  • A pattern can bind names to values extracted from the scrutinee, which are then in scope within the branch associated with that pattern.
  • Since it's a dynamic language, there is no static check to ensure the patterns are exhaustive; it's an error at runtime if the scrutinee doesn't match any of them.
  • "Or" patterns; pattern1 | pattern2 is a pattern which matches if either of the sub-patterns matches ─ again, in order of priority.
  • "Spread" patterns; for example, [$head, *$tail] matches a list with at least one element.

Some more unusual things about pattern-matching in Papyri:

  • HTML tag patterns, like <$tag_name id=$id> $body </>. This would match a tag of any name, with an id attribute and no other attributes, and any contents; these would be bound to the variables $tag_name, $id and $body respectively, but they could be arbitrary other patterns.
  • HTML content patterns, like {Hello, <span>$name</span>!}. This would match an HTML sequence consisting of the text "Hello, ", a span tag with no attributes and any contents, and the text "!".
  • Equality patterns, like =$x. This matches if the value equals the result of the given expression. The expression may use variables which are bound already by other parts of the same pattern.
  • "And" patterns, like pattern1 & pattern2. This matches if both patterns individually match; it is useful for things like $x & [$a, $b, $c], where you want to bind a list to the name $x while also binding its members to other names.
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .