Sweet Egison

The Sweet Egison is a shallow embedding implementation of non-linear pattern matching with extensible and polymorphic patterns [1]. This library desguars the Egison pattern-match expressions into Haskell programs that use non-deterministic monads. This library provides a base of the pattern-match-oriented (PMO) programming style [2] for Haskell users at a practical level of efficiency.

Getting started

We code the equivalent pattern match of case [1, 2, 3] of x : xs -> (x, xs) in this library as follows:

> matchAll dfs [1, 2, 3] (List Something) [[mc| $x : $xs -> (x, xs) |]]
[(1,[2,3])]

Here, we can only observe the small syntactic difference in pattern expressions: the variable bindings are prefixed with $. (We'll come back to List Something later.) You may notice that matchAll returns a list. In our library, pattern matching can return many results. See the following example that doubles all elements in a list:

> take 10 $ matchAll dfs [1 ..] (List Something) [[mc| _ ++ $x : _ -> x * 2 |]]
[2,4,6,8,10,12,14,16,18,20]

++ is the join operator that decomposes a list into an initial prefix and the remaining suffix. We can implement map with pattern matching using this:

> map f xs = matchAll dfs xs (List Something) [[mc| _ ++ $x : _ -> f x |]]
> map (*2) [1,2,3]
[2,4,6]

Note that we don't see any recursions or folds in our map definition! An intuition of map function, that applies the function to all elements, are expressed directly in the pattern expression.

Matchers

Because our pattern matching can return many results, we can use it to decompose non-free data types such as multisets and sets. For example:

> matchAll dfs [1, 2, 3] (Multiset Something) [[mc| $x : $xs -> (x, xs) |]]
[(1,[2,3]),(2,[1,3]),(3,[1,2])]

We use Multiset Something instead of List Something here to match the target [1, 2, 3] as a multiset. These parameters such as Multiset Something, List (List Something), and Something are called matchers and specify pattern-matching methods. Given a matcher m, Multiset m is a matcher for multisets that matches its elements with m. Something is a matcher that provides simple matching methods for an arbitrary value.

Controlling matching strategy

Some pattern matching have infinitely many results and matchAll is designed to be able to enumerate all the results. For this purpose, matchAll traverses a search tree for pattern matching in the breadth-first order. The following example illustrates this:

> take 10 $ matchAll dfs [1 ..] (Set Something) [[mc| $x : $y : _ -> (x, y) |]]
[(1,1),(2,1),(1,2),(3,1),(1,3),(2,2),(1,4),(4,1),(1,5),(2,3)]

We can use the depth-first search with matchAllDFS.

> take 10 $ matchAll dfs [1 ..] (Set Something) [[mc| $x : $y : _ -> (x, y) |]]
[(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(1,10)]

In most cases, the depth-first search is faster than the default breadth-first search strategy. It is recommended to always use matchAllDFS if it is OK to do so.

With matchAllDFS, we can define an intuitive pattern-matching version of concat function on lists.

> concat xs = matchAll dfs xs (List (List Something)) [[mc| _ ++ (_ ++ $x : _) : _ -> x |]]
> concat [[1,2], [3,4,5]]
[1,2,3,4,5]

Non-linear patterns

The non-linear pattern is another powerful pattern-matching feature. It allows us to refer the value bound to variables appear in the left side of the pattern. We provide a pattern syntax named value patterns in the form of #e. The Eql matcher enables value patterns to match with targets that are equal to the corresponding expression. For example, the following example enumerates (p, p+2) pairs of primes:

> import Data.Numbers.Primes ( primes )
> take 10 $ matchAll bfs primes (List Eql) [[mc| _ ++ $p : #(p + 2) : _ -> (p, p+2) |]]
[(3,5),(5,7),(11,13),(17,19),(29,31),(41,43),(59,61),(71,73),(101,103),(107,109)]

We can implement a pattern-matching version of set functions such as member and intersect in a declarative way using non-linear patterns. Match clauses are monoids and can be concatenated using <>.

> member x xs = matchDFS xs (Multiset Eql) [[mc| #x : _ -> True |], [mc| _ -> False |]]
> member 1 [3,4,1,4]
True
> intersect xs ys = matchAll dfs (xs, ys) (Pair (Set Eql) (Set Eql)) [[mc| ($x : _, #x : _) -> x |]]
> intersect [1,2,3] [4,5,3,2]
[2,3]

Further readings

Some practical applications of PMO such as a SAT solver are placed under example/. Detailed information of Egison, the original PMO language implementation, can be found on [https://www.egison.org/](https://www.egison.org/) or in [1]. You can learn more about pattern-match-oriented programming style in [2].

Implementation / Difference from miniEgison

miniEgison is also a Haskell library that implements Egison pattern matching. The main difference from miniEgison is that sweet-egison translates pattern matching into Haskell control expressions (shallow embedding), where miniEgison translates it into Haskell data expressions (deep embedding).

Our quasi-quoter mc translates match clauses into functions that take a target and return a non-deterministic computation as MonadPlus-like monadic expression. As MonadPlus can express backtracking computation, we can perform efficient backtracking pattern matching that is essential to PMO programming on it.

For example, [mc| $xs ++ $x : $ys -> (xs, x, ys) |] is translated as follows:

\tgt ->
  join tgt >-> \(xs, d0) ->
    cons d0 >-> \(x, ys) ->
      pure (xs, x, ys)

\(mat, tgt) ->
  join mat tgt >>= \((m0, m1), (xs, d0)) ->
    cons m1 d0 >>= \((m2, m3), (x, ys)) ->
      pure (xs, x, ys)

-- $hs ++ $ts -> (hs, ts)
\tgt ->
  join tgt >>= \(hs, ts) ->
     pure (hs, ts)

: and ++ are synonyms of cons and join respectively, and desugared in that way during translation. Here, pattern constructor names such as join and cons are overloaded over matchers of collections to archive the ad-hoc polymorphism of patterns.

Bibliography

• [1] Satoshi Egi and Yuichi Nishiwaki: Functional Programming in Pattern-Match-Oriented Programming Style, The Art, Science, and Engineering of Programming, 2020, Vol. 4, Issue 3, Article 7, DOI: 10.22152/programming-journal.org/2020/4/7
• [2] Satoshi Egi and Yuichi Nishiwaki: Non-linear Pattern Matching with Backtracking for Non-free Data Types, APLAS 2018 - Asian Symposium on Programming Languages and Systems, DOI: 11.1007/978-3-030-02768-1_1