3Introduction to Pattern-Match-Oriented Programming

This chapter explains what kind of programming is possible using the syntax for pattern matching and the various built-in patterns introduced in Chapter 2. To that end, we present frequently occurring patterns in programming that leverages Egison pattern matching. We hope this chapter gives you a concrete picture of programming with Egison's pattern matching.

3.1List Programming with Pattern Matching

This section observes how list programming changes with Egison's pattern matching. Here, by list programming, we mean the kind of programming involved in defining functions typically provided by the list libraries of general programming languages, including functional programming languages. The join pattern _ ++ $x :: _, whose second argument is a cons pattern, appears frequently in list programming. For this reason, we have given this pattern a name and call it the join-cons pattern. As this section shows, many functions on lists can be defined using the join-cons pattern.

3.1.1A Single Join-Cons Pattern — the map Function and Its Relatives

For the list matcher, the pattern _ ++ $x :: _ matches each element of the target. As a result, the following matchAll expression matches each element of xs and returns the result of applying the function f to each of them. This is precisely the definition of the map function. The type annotation indicates that the map function takes a list of an arbitrary type a and returns a list of type b.

def map (f: a -> b) (xs: [a]) : [b] := matchAll xs as list something with
  | _ ++ $x :: _ -> f x

By modifying this matchAll expression, we can define various functions. For example, the filter function can be defined by inserting a predicate pattern. The type annotation indicates that the predicate function pred takes a value of type a and returns a Bool.

def filter (pred: a -> Bool) (xs: [a]) : [a] := matchAll xs as list something with
  | _ ++ (?pred & $x) :: _ -> x

The member function can be defined by inserting a value pattern. The member function is a predicate that determines whether the first argument is contained in the collection given as the second argument. The member function is defined using a match expression. The match expression is implemented as an alias for car (matchAll ...)car is a function that extracts the first element of a collection.. This implementation is possible because Egison lazily evaluates matchAll expressions.

The type annotation indicates that the member function takes a value and a list of an arbitrary type a and returns a Bool.

def member (x: a) (xs: [a]) : Bool := match xs as list eq with
  | _ ++ #x :: _ -> True
  | _            -> False

}

The delete function can be implemented by slightly modifying the member function. The delete function removes the first occurrence of the first argument x from the collection xs given as the second argument.

def delete (x: a) (xs: [a]) : [a] := match xs as list eq with
  | $hs ++ #x :: $ts -> hs ++ ts
  | _                -> xs

}

The predicates any and every can similarly be implemented using match expressions. any is a predicate that determines whether any element in the collection given as the second argument satisfies the predicate given as the first argument. every is a predicate that determines whether all elements in the collection given as the second argument satisfy the predicate given as the first argument.

def any (pred: a -> Bool) (xs: [a]) : Bool := match xs as list something with
  | _ ++ ?pred :: _ -> True
  | _               -> False

def every (pred: a -> Bool) (xs: [a]) : Bool := match xs as list something with
  | _ ++ !?pred :: _ -> False
  | _                -> True

3.1.2Nesting Join-Cons Patterns — the unique and concat Functions

By combining multiple join-cons patterns, we can create even more powerful patterns. As an example, we introduce the unique function. When the unique function is defined using pattern-match-oriented programming, it looks as follows. The type annotation indicates that the unique function takes a list of an arbitrary type a and returns a list of the same type.

def unique (xs: [a]) : [a] := matchAllDFS xs as list eq with
  | _ ++ $x :: !(_ ++ #x :: _) -> x

The not pattern is used to express that x does not appear any further after itself. As a result, this pattern matches the last occurrence of each element.

unique [1,2,3,2,4] -- [1,3,2,4]

It is also possible to define a unique function that returns a collection consisting of the first occurrence of each element by making good use of predicate patterns. To match only the first occurrence, we need to write a pattern that matches when the same element does not appear before that element. Because Egison's pattern matching processes patterns from left to right, such a pattern cannot be written by simply combining cons patterns and join patterns.

def unique2 (xs: [a]) : [a] := matchAllDFS xs as list eq with
  | $hs ++ (!?(\x -> member x hs) & $x) :: _ -> x

unique2 [1,2,3,2,4] -- [1,2,3,4]

Another more elegant approach is to use sequential patterns. The same pattern can be expressed using a sequential pattern with a deferred pattern variable in the first argument of the join pattern.

def unique (xs: [a]) : [a] := matchAllDFS xs as list eq with
  |  {@               ++ $x :: _,
      !(_ ++ #x :: _)}
  -> x

Another example of nested join-cons patterns is the concat function introduced in Section 2.5 of Chapter 2. By combining matcher composition (Section 2.10 of Chapter 2) with the join-cons pattern, we can define concat using pattern-match-oriented programming. The type annotation indicates that the concat function takes a list of lists and returns a flattened list.

def concat (xss: [[a]]) : [a] := matchAllDFS xss as list (list something) with
  | _ ++ (_ ++ $x :: _) :: _ -> x

3.2Multiset Programming

The ability to directly pattern-match on multisets is a major feature of Egison. This section introduces techniques for programming that takes advantage of multiset pattern matching. From this point on, nearly all pattern matching in this book involves multiset pattern matching.

3.2.1Cons Patterns on Multisets

The cons pattern of the multiset matcher is useful for pattern matching on collections while ignoring the order of elements. Such situations frequently arise when describing mathematical algorithms.

Let us start with a simple example. The lookup function on association lists can be defined with a single cons pattern. A single multiset cons pattern can also be replaced with a list join-cons pattern. The type annotation indicates that the lookup function takes a key k and an association list and returns the corresponding value.

def lookup (k: a) (ls: [(a, b)]) : b := match ls as multiset (eq, something) with
  | (#k, $x) :: _ -> x

However, nested multiset cons patterns cannot be replaced with list join-cons patterns. A \(k\)-fold nested multiset cons pattern can be used to enumerate \(P(n,k) = \frac{n!}{(n-k)!}\) permutations of \(k\) elements, whereas a \(k\)-fold nested list join-cons pattern can be used to enumerate \(C(n,k) = \frac{n!}{k!(n-k)!}\) combinations of \(k\) elements.

matchAll [1, 2, 3] as list something with
| _ ++ $x :: _ ++ $y :: _ -> (x, y)
-- [(1,2),(1,3),(2,3)]

matchAll [1, 2, 3] as multiset something with
| $x :: $y :: _ -> (x, y)
-- [(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)]

An equivalent program can be written in traditional functional programming using list comprehensions as follows. tails is a function that returns the suffixes of the argument list. splits is a function that decomposes the argument list into a prefix and the remaining list.

[ (x, y) | x : ts <- tails [1, 2, 3], y <- ts ]
-- [(1,2),(1,3),(2,3)]

[ (x, y) | (hs, x : ts) <- splits [1, 2, 3], y <- hs ++ ts ]
-- [(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)]

Although traditional programming languages also provide libraries for multisets, there are many situations where collections that one wants to treat as multisets must be reconsidered as lists. In fact, in the enumeration of \(C(n,2)\) combinations using list comprehensions above, two list-processing functions—splits and ++—are used, describing processing that reconsiders the target collection as a list. Pattern matching on multisets hides such list-based reconversion inside the pattern definition (in this case, the definition of the :: pattern of the multiset matcher), thereby broadening the opportunities to directly treat collections that one wants to handle as multisets. The remainder of this book describes various patterns on multisets, combined with the patterns introduced in Chapter 2.

3.2.2Poker Hand Evaluation

As an application of non-linear patterns on multisets, we present poker hand evaluation. Using non-linear patterns on multisets, every poker hand can be expressed as a single pattern. When the author designed Egison's match expressions, the ability to concisely write a program for poker hand evaluation was one of the design requirements. The pattern “[\(p_1\), \(p_2\), \(...\), \(p_n\)]” is syntactic sugar that expands to “\(p1\) : \(p_2\) : \(...\) : \(p_n\) : []”.

def poker (cs: [Card]) : String :=
  match cs as multiset card with
  | card $s $n :: card #s #(n-1) :: card #s #(n-2) :: card #s #(n-3) :: card #s #(n-4) :: _
    -> "Straight flush"
  | card _ $n :: card _ #n :: card _ #n :: card _ #n :: _ :: []
    -> "Four of a kind"
  | card _ $m :: card _ #m :: card _ #m :: card _ $n :: card _ #n :: []
    -> "Full house"
  | card $s _ :: card #s _ :: card #s _ :: card #s _ :: card #s _ :: []
    -> "Flush"
  | card _ $n :: card _ #(n-1) :: card _ #(n-2) :: card _ #(n-3) :: card _ #(n-4) :: []
    -> "Straight"
  | card _ $n :: card _ #n :: card _ #n :: _ :: _ :: []
    -> "Three of a kind"
  | card _ $m :: card _ #m :: card _ $n :: card _ #n :: _ :: []
    -> "Two pair"
  | card _ $n :: card _ #n :: _ :: _ :: _ :: []
    -> "One pair"
  | _ :: _ :: _ :: _ :: _ :: [] -> "Nothing"

This poker function works as follows.

poker [Card Spade 5, Card Spade 6, Card Spade 7, Card Spade 8, Card Spade 9]
-- "Straight flush"
poker [Card Spade 5, Card Diamond 5, Card Spade 7, Card Club 5, Card Heart 5]
-- "Four of a kind"
poker [Card Spade 5, Card Diamond 5, Card Spade 7, Card Club 5, Card Heart 7]
-- "Full house"
poker [Card Spade 5, Card Spade 6, Card Spade 7, Card Spade 13, Card Spade 9]
-- "Flush"
poker [Card Spade 5, Card Club 6, Card Spade 7, Card Spade 8, Card Spade 9]
-- "Straight"
poker [Card Spade 5, Card Diamond 5, Card Spade 7, Card Club 5, Card Heart 8]
-- "Three of a kind"
poker [Card Spade 5, Card Diamond 10, Card Spade 7, Card Club 5, Card Heart 10]
-- "Two pair"
poker [Card Spade 5, Card Diamond 10, Card Spade 7, Card Club 5, Card Heart 8]
-- "One pair"
poker [Card Spade 5, Card Spade 6, Card Spade 7, Card Spade 8, Card Diamond 11]
-- "Nothing"

Egison has a rule that pattern constructors (such as card) begin with a lowercase letter, while data constructors (such as Card) begin with an uppercase letter. The type annotation of the poker function indicates that it takes a list of cards and returns a string representing the hand.

Note that in the above example, the card matcher is defined as an algebraic data matcher as follows.

def suit := algebraicDataMatcher
  | spade
  | heart
  | club
  | diamond

def card := algebraicDataMatcher
  | card suit (mod 13)

3.3Comparing Data with Tuple Patterns

Situations where one wants to compare multiple pieces of data arise frequently in programming. In such situations, tuple patterns, especially when used together with not patterns, are often useful. For example, the difference function can be defined by inserting a not pattern into the implementation of the intersect function introduced in Section 2.10 of Chapter 2. The type annotation indicates that the function takes two sets and returns their difference.

def difference (xs: [a]) (ys: [a]) : [a] := matchAll (xs, ys) as (set eq, set eq) with
  | ($x :: _, !(#x :: _)) -> x

By changing the insertion position of the not pattern to !($x :: _, #x :: _), we can also write a pattern that succeeds when the two collections have no common elements at all.

By combining these patterns with sequential patterns, we can write even more complex patterns. This is because sequential patterns make it possible to apply a not pattern collectively to multiple separate parts of a pattern. For example, in Section 2.8 of Chapter 2, we defined the singleCommonElem function, which checks whether two collections have exactly one common element, using pattern matching. Sequential not patterns sometimes become necessary when describing mathematical algorithms. For instance, sequential not patterns also appear in the SAT solver implementation introduced in Section 4.1 of Chapter 4. The type annotation indicates that the function takes two lists and returns a boolean.

def singleCommonElem (xs: [a]) (ys: [a]) : Bool := match (xs, ys) as (multiset eq, multiset eq) with
                    | [($x :: @, #x :: @),
                       !($y :: _, #y :: _)] -> True
                    | _ -> False

It is also possible to combine sequential patterns with loop patterns. For example, a pattern that matches the common prefix of two lists can be written using a sequential loop pattern.

match (xs, ys) as (list eq, list eq) with
| loop $i (1,$n)
    [($x_i :: @, #x_i :: @), [...]]
    !($y :: _, #y :: _)
-> map (\i -> x_i) [1..n]

3.4Recursive Patterns with Loop Patterns

Loop patterns are used to express repetition of patterns. Loop patterns are useful for constructing complex patterns by combining simple pattern constructors, or for writing patterns in which the number of pattern variables depends on a parameter. In such situations, complex recursion needs to be written. With loop patterns, such recursion can be pushed into the pattern, enabling intuitive descriptions. This section presents such examples.

3.4.1The N-Queens Problem

This section introduces a technically sophisticated yet tricky example of loop patterns by presenting a program that solves the N-Queens problem. The N-Queens problem is the problem of placing \(n\) chess queens on an \(n \times n\) chessboard so that no two queens threaten each other. A chess queen can attack any piece that is any number of squares away horizontally, vertically, or diagonally. In terms of Japanese chess (shogi), the queen combines the moves of the rook and the bishop.

Let us start with a program that solves the \(4\)-Queens problem. In this program, the placement of the \(4\) queens is represented as a list. The \(n\)-th element of the list represents which column the queen in the \(n\)-th row is placed in. In this case, the solution must be a permutation of the elements of the collection [1,2,3,4], because no two queens can be placed in the same row or column. Therefore, we pattern-match the collection [1,2,3,4] as a multiset of integers. The condition that queens cannot share a diagonal line is expressed by the conditions \(a_1 \pm 1 \neq a_2\), \(a_1 \pm 2 \neq a_3\), \(a_2 \pm 1 \neq a_3\), \(a_1 \pm 3 \neq a_4\), \(a_2 \pm 2 \neq a_4\), and \(a_3 \pm 1 \neq a_4\).

matchAll [1,2,3,4] as multiset integer with
  $a_1 ::
   (!#(a_1 - 1) & !#(a_1 + 1) & $a_2) ::
    (!#(a_1 - 2) & !#(a_1 + 2) & !#(a_2 - 1) & !#(a_2 + 1) & $a_3) ::
     (!#(a_1 - 3) & !#(a_1 + 3) & !#(a_2 - 2) & !#(a_2 + 2) & !#(a_3 - 1) & !#(a_3 + 1) & $a_4) ::
      [] -> [a_1,a_2,a_3,a_4]
-- [[2,4,1,3],[3,1,4,2]]

To generalize the above program for the \(n\)-Queens problem, doubly nested loop patterns can be used. The index variable i of the outer loop pattern is used in the index range of the inner loop pattern to express the difference in the number of repetitions of the inner loop. Also note that values bound in previous repetition patterns, for example the value bound to $a_j, are referenced as in #(a_j - (i - j)) and #(a_j + (i - j)). In this way, the non-linearity of indexed pattern variables (the ability to reference values bound to indexed pattern variables on the left side of the pattern) works effectively. The type annotation indicates that the nQueens function takes an integer n and returns a list of lists of integers.

def nQueens (n: Integer) : [[Integer]] :=
  matchAll [1..n] as multiset integer with
  | $a_1 ::
     (loop $i (2,n)
           ((loop $j (1, i - 1)
                  (!#(a_j - (i - j)) & !#(a_j + (i - j)) & ...)
                  $a_i) :: ...)
           [] -> map (\i -> a_i) [1..n]

nQueens 4 -- [[2,4,1,3],[3,1,4,2]]

3.4.2Pattern Matching on Trees

This section introduces a practical example of loop patterns by demonstrating pattern matching on trees. The tree nodes in this section can have an arbitrary number of subtrees as children, similar to XML. Furthermore, these subtrees are treated as multisets. A matcher for such trees was defined in Section 2.10 of Chapter 2. We use that matcher in this section.

We write patterns against a tree that categorizes programming languages. treeData defines that category tree. For example, "Egison" belongs to the "pattern-match-oriented" category and to the "Dynamically typed" subcategory of the "Functional language" category. Data constructors Node and Leaf begin with uppercase letters.

def treeData :=
  Node "Programming language"
    [Node "pattern-match-oriented" [Leaf "Egison"],
     Node "Functional language"
       [Node "Strictly typed" [Leaf "OCaml", Leaf "Haskell", Leaf "Curry", Leaf "Coq"],
        Node "Dynamically typed" [Leaf "Egison", Leaf "Lisp", Leaf "Scheme", Leaf "Racket"]],
     Node "Logic programming" [Leaf "Prolog", Leaf "Curry"],
     Node "Object oriented" [Leaf "C++", Leaf "Java", Leaf "Ruby", Leaf "Python", Leaf "OCaml"]]

The following matchAll expression enumerates the categories to which a given language belongs. Because a leaf of the tree can be at any depth, a loop pattern whose index range end value is a pattern (in this case $n) is used. The ellipsis pattern of this loop pattern is positioned not at the end of the repetition pattern. The ability for users to specify the position of repetition is another strength of loop patterns that the Kleene star operator of regular expressions does not have. Pattern constructors node and leaf begin with lowercase letters. The type annotation indicates that the ancestors function takes a string x and a tree t and returns a list of ancestor node paths.

def ancestors (x: String) (t: Tree String) : [[String]] := matchAll t as tree string with
  | loop $i (1,$n)
      (node $c_i (... ::  _))
      (leaf #x)
  -> map (\i -> c_i) [1..n]

ancestors "Egison" treeData
-- [["Programming language", "pattern-match-oriented"], ["Programming language", "Functional language", "Dynamically typed"]]

It is also possible to write a pattern that enumerates all languages belonging to a given subcategory. By using doubly nested loop patterns, the subcategory can be at any depth. The following pattern enumerates all languages belonging to a specific category. matchAllDFS is used to enumerate languages in the same order as they appear in the tree. The type annotation indicates that the descendants function takes a string x and a tree t and returns a list of descendant nodes.

def descendants (x: String) (t: Tree String) : [String] := matchAllDFS t as tree string with
  | loop _ (1,_)
      (node _ (... ::  _))
      (node #x ((loop _ (1,_)
                   (node _ (... :: _))
                   (leaf $y)) :: _))
  -> y

descendants "Functional language" treeData
-- ["OCaml", "Haskell", "Curry", "Coq", "Egison", "Lisp", "Scheme", "Racket"]

A DSL (domain-specific language) capable of pattern matching on trees is XML Path. An advantage of Egison is that a wide variety of patterns can be described by combining a small number of user-definable pattern constructors with loop patterns. XML Path, by contrast, uses many built-in commands such as the ancestor command to describe patterns.

3.4.3Pattern Matching on Graphs

This section introduces pattern matching on graphs. We present pattern matching on both graphs represented as sets of edges and graphs represented as adjacency lists.

Graphs as Sets of Edges

This section performs pattern matching on graphs represented as sets of edges. First, we define the following matcher and graph.

def graph := set edge
def edge := algebraicDataMatcher
  | edge integer integer

def graphData :=
  [ Edge 1 2, Edge 2 1, Edge 2 3,  Edge 2 4, Edge 3 4, Edge 4 5, Edge 4 6, Edge 4 7
  , Edge 5 4, Edge 5 6, Edge 5 7,  Edge 6 4, Edge 6 5, Edge 6 7, Edge 7 4, Edge 7 5
  , Edge 7 6, Edge 7 8, Edge 9 10, Edge 10 7 ]

The pattern constructor edge begins with a lowercase letter, while the data constructor Edge begins with an uppercase letter. Figure 3.4.3 shows a visualization of the above graph. This section presents several pattern matches on this graph.

A pattern that enumerates all nodes reachable from a given node s by traversing two edges can be written as follows.

let s := 1 in
  matchAll graphData as graph with
  | edge (#s & $x_1) $x_2 :: edge #x_2 $x_3 :: _
  -> x
-- [1,3,4,5,6,7]

A pattern that enumerates nodes connected to node s via an edge originating from s, but which do not themselves have an edge back to s, can be written using a not pattern as follows.

let s := 1 in
  matchAll graphData as graph with
  | edge #s $x :: !(edge #x #s :: _)
  -> x
-- [4]

A pattern that enumerates all paths from node s to node e can be written using a loop pattern. Egison allows the use of let expressions within patterns. This let expression is used to bind s to $x_1. Thanks to this let expression, the first repetition of the loop pattern does not need to be treated as a special case.

let (s, e) := (1, 8) in
  matchAll graphData as graph with
  | let x_1 := s in
      loop $i (2, $n)
           (edge #x_(i - 1) $x_i :: ...)
           (edge #x_(n - 1) (#e & $x_n) :: _)
  -> map (\i -> x_i) [1..n]
-- [[1,4,7,8], ...]

A pattern that enumerates cliques (subgraphs forming complete graphs) of size \(n\) can be written as follows. It uses doubly nested loop patterns.

let n := 4 in
  matchAll graphData2 as graph with
  | edge $x_1 $x_2 :: loop $i (3, n)
                           (edge #x_1 $x_i :: loop $j (2, i - 1)
                                                   (edge #x_j #x_i :: ...)
                                                   ...)
                          _
  -> map (\i -> x_i) [1..n]
-- [[4,5,6,7],...]

This section presented pattern matching on directed graphs. It is straightforward to modify the above patterns for directed graphs into patterns for undirected graphs: simply use a matcher that identifies Edge a b and Edge b a. Such a matcher for undirected graphs can be defined using the matcher for unordered pairs introduced in Section 6.2 of Chapter 6.

Adjacency Graphs

This section performs pattern matching on graphs represented as weighted adjacency lists. A matcher for weighted adjacency lists can be defined using matcher composition (Section 2.10 of Chapter 2). The graphData in the program below represents a network of cities connected by air routes as a weighted adjacency list. The travel time between two cities is represented as an integer weight.

def graph := multiset (string, multiset (string, integer))

def graphData :=
  [("Berlin", [("New York", 14), ("London", 2), ("Tokyo", 14), ("Vancouver", 13)]),
   ("New York", [("Berlin", 14), ("London", 12), ("Tokyo", 18), ("Vancouver", 6)]),
   ("London", [("Berlin", 2), ("New York", 12), ("Tokyo", 15), ("Vancouver", 10)]),
   ("Tokyo", [("Berlin", 14), ("New York", 18), ("London", 15), ("Vancouver", 12)]),
   ("Vancouver", [("Berlin", 13), ("New York", 6), ("London", 10), ("Tokyo", 12)])]

The pattern in the following program matches routes that depart from Berlin, visit all cities, and return to Berlin. This pattern is used to solve the traveling salesman problem. It makes effective use of non-linear loop patterns. The type annotation indicates that the trips function computes a list of routes from the graph data and returns a list of tuples of total distance and city list.

def trips : [(Integer, [String])] :=
  let n := length graphData in
    matchAll graphData as graph with
    | (#"Berlin", (($s_1,$p_1) :: _)) ::
        loop $i (2, n - 1)
          ((#s_(i - 1), ($s_i, $p_i) :: _) :: ...)
          ((#s_(n - 1), (#"Berlin" & $s_n, $p_n) :: _) :: [])
    -> (sum (map (\i -> p_i) [1..n]), map (\i -> s_i) [1..n])

head (sortBy (\(_, x), (_, y) -> compare x y) trips)
-- (46, ["London", "New York", "Vancouver", "Tokyo", "Berlin"])

As with trees (Section 3.4.2), several DSLs for pattern matching on graphs have been developed as query languages for graph databases. An advantage of Egison over these DSLs is that a wide variety of patterns can be expressed by combining a small number of user-defined pattern constructors with a few built-in patterns, including loop patterns.