/pattern-matching-in-rust

Pattern matching and exhaustiveness checking algorithms implemented in Rust

Primary LanguageRustThe UnlicenseUnlicense

Pattern matching in Rust

This repository contains a collection of pattern matching algorithms implemented in Rust. The goal of these implementations it to (hopefully) make it easier to understand them, as papers related to pattern matching (and papers in general) can be difficult to read.

Background

I ended up implementing these algorithms while investigating potential pattern matching/exhaustiveness checking algorithms for Inko. While there are plenty of papers on the subject, few of them include reference code, and almost all of them are really dense and difficult to read. I hope the code published in this repository is of use to those wishing to implement pattern matching/exhaustiveness.

Algorithms

Name Paper Directory
ML pattern compilation and partial evaluation PDF sestoft1996
How to compile pattern matching PDF jacobs2021

Other papers I've come across (but don't necessarily want to implement):

Requirements

A recent-ish (as of 2022) Rust version that supports the 2021 edition (though I think the 2018 edition should also work).

Usage

Each algorithm is implemented as a library, and come with a set of unit tests that you can run using cargo test.

Licence

The code in this repository is licensed under the Unlicense. A copy of this license can be found in the file "LICENSE".