miniEgison: Template Haskell Implementation of Egison Pattern Matching

This Haskell library provides the users with the pattern-matching facility against non-free data types. Non-free data types are data types whose data have no standard forms. For example, multisets are non-free data types because the multiset {a,b,b} has two other equivalent but literally different forms {b,a,b} and {b,b,a}. This library provides the pattern-matching facility that fulfills the following three criteria for practical pattern matching for non-free data types: (i) non-linear pattern matching with backtracking; (ii) extensibility of pattern-matching algorithms; (iii) ad-hoc polymorphism of patterns.

The design of the pattern-matching facility is originally proposed in this paper and implemented in the Egison programming language.

Grammar

This library provides two syntax constructs, matchAll, match, matchAllDFS, and matchDFS for advanced pattern matching for non-free data types.

e ::= hs-expr                    -- arbitrary Haskell expression
    | matchAll e e [C, ...]      -- match-all expression
    | match e e [C, ...]         -- match expression
    | matchAllDFS e e [C, ...]   -- match-all expression
    | matchDFS e e [C, ...]      -- match expression
    | Something                  -- Something built-in matcher

C ::= [mc| p -> e |]             -- match clause

p ::= _                          -- wildcard pattern
    | $v                         -- pattern variable
    | #e                         -- value pattern
    | ?e                         -- predicate pattern
    | (p_1, p_2, ..., p_n)       -- tuple pattern
    | [p_1, p_2, ..., p_n]       -- collection pattern
    | p & p                      -- and-pattern
    | p | p                      -- or-pattern
    | !p                         -- not-pattern
    | c p_1 p_2 ... p_n          -- constructor pattern

Usage

The matchAll expression and matchers

The matchAll expression evaluates the body of the match clause for all the pattern-matching results. The expression below pattern-matches a target [1,2,3] as a list of integers with a pattern cons $x $xs. This expression returns a list of a single element because there is only one decomposition.

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

The other characteristic of matchAll is its additional argument matcher. A matcher is a special object that retains the pattern-matching algorithms for each data type. matchAll takes a matcher as its second argument. We can change a way to interpret a pattern by changing a matcher.

For example, by changing the matcher of the above matchAll from List Integer to Multiset Integer, the evaluation result changes as follows:

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

When the Multiset matcher is used, : (the cons pattern) decomposes a target list into an element and the rest elements.

The pattern-matching algorithms for each matcher can be defined by users. For example, the matchers such as List and Multiset can be defined by users. The Something matcher is the only built-in matcher. something can be used for pattern-matching arbitrary objects but can handle only pattern variables and wildcards. The definitions of List and Multiset are found here. We will write an explanation of this definition in future.

Non-linear pattern

Non-linear pattern matching is another important feature of Egison pattern matching. Non-linear patterns are patterns that allow multiple occurrences of the same pattern variables in a pattern. For example, the program below pattern-matches a list [1,2,5,9,4] as a multiset and extracts pairs of sequential elements. A non-linear pattern is effectively used for expressing the pattern.

matchAll [1,2,5,9,4] (Multiset Integer) [[mc| $x : #(x+1) : _ -> x|]]
-- [1,4]

The match expression

The match expression takes a target, a matcher, and match-clauses as the matchAll expression. The match expression returns only the evaluation result of the first pattern-matching result.

match [1,2,5,9,4] (Multiset Integer) [[mc| $x : #(x+1) : _ -> x|]]
-- 1

The match expression is simply implemented using matchAll as follows:

match tgt m cs = head $ matchAll tgt m cs

matchAllDFS and matchDFS

The matchAll and match expressions traverse a search tree for pattern matching in breadth-first order. The reason of the default breadth-first traversal is because to enumerate all the successful pattern-matching results even when they are infinitely many. For example, all the pairs of natural numbers can be enumerated by the following matchAll expression:

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

If we change the above matchAll to matchAllDFS, the order of the pattern-matching results changes as follows:

take 10 (matchAllDFS [1..] (Set Integer)
           [[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)]

There are cases where depth-first traversal is suitable because the depth-first order of pattern-matching results is preferable. Furthermore, matchAllDFS is more efficient than matchAll. It would be better to use matchAllDFS instead of matchAll when the both expressions can be used.

Matcher definitions

The users can define pattern-matching algorithms for each pattern by themselves.

preparing...

matchAll (1,2) UnorderedEqlPair [[mc| uepair $x $y -> (x,y) |]]
-- [(1,2),(2,1)]

matchAll (1,2) UnorderedEqlPair [[mc| uepair #2 $x -> x |]]
-- [1]

A matcher is represented as a data type whose name and constructor's name is identical.

preparing...

data UnorderedEqlPair = UnorderedEqlPair
instance (Eq a) -> Matcher UnorderedEqlPair (a, a)

uepair :: (Eq a)
       => Pattern a Eql ctx xs
       -> Pattern a Eql (ctx :++: xs) ys
       -> Pattern (a, a) UnorderedEqlPair ctx (xs :++: ys)
uepair p1 p2 = Pattern (\_ UnorderedEqlPair (t1, t2) ->
                          [twoMAtoms (MAtom p1 Eql t1) (MAtom p2 Eql t2)
                          ,twoMAtoms (MAtom p1 Eql t2) (MAtom p2 Eql t1)])

matchAll (1,2) (UnorderedPair Eql) [[mc| uepair $x $y => (x,y) |]]
-- [(1,2),(2,1)]

matchAll (1,2) (UnorderedPair Eql) [[mc| upair #2 $x => x |]]
-- [1]

data UnorderedPair m = UnorderedPair m
instance Matcher m a => Matcher (UnorderedPair m) (a, a)

upair :: (Matcher m a , a ~ (b, b), m ~ (UnorderedPair m'), Matcher m' b)
      => Pattern b m' ctx xs
      -> Pattern b m' (ctx :++: xs) ys
      -> Pattern a m ctx (xs :++: ys)
upair p1 p2 = Pattern (\_ (UnorderedPair m') (t1, t2) ->
                         [twoMAtoms (MAtom p1 m' t1) (MAtom p2 m' t2)
                         ,twoMAtoms (MAtom p1 m' t2) (MAtom p2 m' t1)])

Samples

Twin primes

We can extract all twin primes from the list of prime numbers by pattern matching:

take 10 (matchAll primes (List Integer)
           [[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)]

It is also possible to enumerate all the pairs of prime numbers whose form is (p, p+6):

take 10 (matchAll primes (List Integer)
           [[mc| _ ++ $p : _ ++ #(p+6) : _ -> (p, p+6) |]])
-- [(5,11),(7,13),(11,17),(13,19),(17,23),(23,29),(31,37),(37,43),(41,47),(47,53)]

Poker hand

poker cs =
  match cs (Multiset CardM)
    [[mc| card $s $n :
           card #s #(n-1) :
            card #s #(n-2) :
             card #s #(n-3) :
              card #s #(n-4) :
               [] -> "Straight flush" |],
     [mc| card _ $n :
           card _ #n :
            card _ #n :
             card _ #n :
              _ :
               [] -> "Four of a kind" |],
     [mc| card _ $m :
           card _ #m :
            card _ #m :
             card _ $n :
              card _ #n :
               [] -> "Full house" |],
     [mc| card $s _ :
           card #s _ :
            card #s _ :
             card #s _ :
              card #s _ :
               [] -> "Flush" |],
     [mc| card _ $n :
           card _ #(n-1) :
            card _ #(n-2) :
             card _ #(n-3) :
              card _ #(n-4) :
               [] -> "Straight" |],
     [mc| card _ $n :
           card _ #n :
            card _ #n :
             _ :
              _ :
               [] -> "Three of a kind" |],
     [mc| card _ $m :
           card _ #m :
            card _ $n :
             card _ #n :
              _ :
               [] -> "Two pair" |],
     [mc| card _ $n :
           card _ #n :
            _ :
             _ :
              _ :
               [] -> "One pair" |],
     [mc| _ -> "Nothing" |]]

Benchmark

We benchmarked this library using the program that enumerates the first 100 twin primes. This Haskell library is faster (more than 20 times in this case) than the original Egison interpreter!

$ cat benchmark/prime-pairs-2.hs
{-# LANGUAGE QuasiQuotes     #-}
{-# LANGUAGE GADTs           #-}

import Control.Egison
import Data.Numbers.Primes

main :: IO ()
main = do
  let n = 100
  let ans = take n (matchAll primes (List Integer)
                     [[mc| _ ++ $p : #(p+2) : _ -> (p, p+2) |]])
  putStrLn $ show ans
$ stack ghc -- benchmark/prime-pairs-2.hs
$ time ./benchmark/prime-pairs-2
[(3,5),(5,7),(11,13), ..., (3671,3673),(3767,3769),(3821,3823)]
./benchmark/prime-pairs-2  0.01s user 0.01s system 64% cpu 0.024 total

$ cat benchmark/prime-pairs-2.egi
(define $n 100)
(define $primes {2 3 5 7 11 13 17 ... 4391 4397 4409})

(define $twin-primes
  (match-all primes (list integer)
    [<join _ <cons $p <cons ,(+ p 2) _>>>
     [p (+ p 2)]]))

(take n twin-primes)
$ time stack exec egison -- -t benchmark/prime-pairs-2.egi
{[3 5] [5 7] [11 13] ... [3671 3673] [3767 3769] [3821 3823]}
stack exec egison -- -t benchmark/prime-pairs-2.egi  0.54s user 0.04s system 97% cpu 0.593 total

Sponsors

Egison is sponsored by Rakuten, Inc. and Rakuten Institute of Technology.