8Sweet Egison -- A Haskell Library for Egison Pattern Matching
In addition to the Egison language implementation introduced so far in this book, Egison pattern matching has also been implemented as a library in the form of a Domain Specific Language (DSL) on top of existing languages. Library implementations on existing languages come in two types: the miniEgison family, which uses deep embedding (a technique that realizes a DSL by embedding an interpreter), and the Sweet Egison family, which uses shallow embedding (a technique that realizes a DSL by embedding a compiler). This chapter introduces how to use the Haskell implementation of Sweet Egison, the fastest among these implementations. Unlike Egison, Haskell has a static type system. Therefore, pattern matching using Sweet Egison is type-checked at compile time.
8.1Using Sweet Egison
Sweet Egison is published as a Haskell library through Hackage. This section explains how to use Sweet Egison, assuming it is already installed.
Sweet Egison has a matchAll expression just like Egison. matchAll takes a search strategy, a target matcher, and a list of match clauses as arguments. In Sweet Egison, matchAll is implemented as a Haskell function, so keywords such as as and with are not used.
matchAll dfs [1, 2, 3] (List Something)
[[mc| $x : $xs -> (x, xs) |]]
-- [(1, [2, 3])]The above matchAll expression specifies depth-first search dfs as its search strategy. In Sweet Egison, users can define new search strategies. This is a feature of Sweet Egison that Egison does not have. How to define search strategies is explained in Section 8.6. The matcher of the above matchAll expression is (List Something). As will be explained again in Section 8.5, matchers in Sweet Egison are represented as Haskell data. Match clauses are expressed using the mc quasi-quoter. A quasi-quoter is a feature provided by Template Haskell, where the part enclosed by [mc| and |] is received as a string, and by defining a function that returns a Haskell program, users can perform Haskell metaprogramming. What kind of Haskell program match clauses are expanded into is introduced in Section 8.2. The cons pattern is represented by a single colon, just as in Haskell.
The search strategies defined in the library from the start are depth-first search dfs and breadth-first search bfs. Depth-first search dfs may not be able to enumerate all infinitely many pattern-matching results, but it is fast.
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)]Breadth-first search bfs can enumerate all infinitely many pattern-matching results, but it is less efficient than depth-first search dfs.
take 10 (matchAll bfs [1..] (Set Something)
[[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)]The reason matchAll takes a list of match clauses as its argument is to handle multiple match clauses. Just as in Egison, “matchAll \(t\) \(m\) [\(c_1\),\(c_2\),\(...\)]” is equivalent to “matchAll \(t\) \(m\) [\(c_1\)] ++ matchAll \(t\) \(m\) [\(c_2\)] ++ \(...\)”.
matchAll [1, 2, 3] (List Something)
[[mc| $x : $xs -> (x, xs) |]
,[mc| _ : $x : $xs -> (x, xs) |]]
-- [(1, [2, 3]), (2, [3])]In Sweet Egison, value patterns are expressed using #, just as in Egison. Non-linear patterns can be expressed using value patterns.
matchAll [1, 5, 2, 4] (Multiset Eql)
[[mc| $x : #(x + 1) : _ -> (x, x + 1) |]]
-- [(1, 2), (4, 5)]Sweet Egison also implements match, which returns only the first pattern-matching result. match is defined using matchAll as follows.
match s tgt m cs = head (matchAll s tgt m cs)Using match, a poker hand evaluator can be written as shown in Figure 8.1. In Sweet Egison, since data constructors are used for both the target data type and the matcher, name collisions of data constructors tend to occur. Therefore, it is common to append M (for matcher) to the end, such as CardM, to avoid name collisions.
data Suit = Spade | Heart | Club | Diamond deriving (Eq)
data Card = Card Suit Integer
poker :: [Card] -> String
poker cs =
matchDFS 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" |]]
8.2How Sweet Egison Works
To explain the idea behind the implementation of Sweet Egison, let us first see what kind of Haskell program the following matchAll expression is transformed into. cons $x _ is a pattern equivalent to $x : _. In Sweet Egison, only : and ++ are implemented as built-in infix operators. For clarity, this section uses prefix notation for cons patterns.
matchAll dfs [1, 2, 3] (Multiset Something) [[mc| cons $x _ -> x |]]The above program is expanded into the following do expression for the list monad.
(\ (matcher, target) -> do
(x, _) <- cons matcher target
let (_, _) = consM matcher target
return x)
(Multiset Something, [1, 2, 3]) -- [1, 2, 3]cons and consM appearing in the expanded program are functions for computing next targets and next matchers, respectively. cons and consM are functions defined in Haskell. cons and consM take a matcher and a target as arguments. The reason they take a matcher as an argument is to realize polymorphism of patterns.
cons (Multiset Something) [1, 2, 3] -- [(1, [2, 3]), (2, [1, 3]), (3, [1, 2])]
consM (Multiset Something) [1, 2, 3] -- (Something, Multiset Something)matchAll dfs [1, 2, 3] (Multiset Something) [[mc| cons $x (cons $y _) -> (x, y) |]]
-- [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3,2)](\ (matcher, target) -> do
(x, target') <- cons matcher target
let (_, matcher') = consM matcher target
(y, _) <- cons matcher' target'
let (_, _) = consM matcher' target'
return (x, y))
(Multiset Something, [1, 2, 3])Let us also look at the expansion of a pattern containing a value pattern.
matchAll dfs [1, 2, 3] (Multiset Eql)
[[mc| cons $x (cons #(x * 2) _) -> (x, y) |]]
-- [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3,2)]valuePat is a function defined in Haskell, just like the cons function introduced earlier.
(\ (matcher, target) -> do
(x, target') <- cons matcher target
let (_, matcher') = consM matcher target
(target'', _) <- cons matcher' target'
let (matcher'', _) = consM matcher' target'
valuePat (x * 2) matcher'' target''
return (x, y))
(Multiset Something, [1, 2, 3])8.3Optimizations in Sweet Egison
The actual Sweet Egison performs slightly more complex expansions than those explained in Section 8.2, for optimization purposes. In particular, there are special techniques for wildcard optimization. This section introduces these techniques.
8.3.1Optimization of Wildcard Pattern Matching
The wildcard optimization described in Section 6.6 can also be performed in Sweet Egison. Wildcard optimization speeds up pattern matching by omitting the computation of targets that match wildcards in patterns containing wildcards. This section explains how to use this optimization in Sweet Egison, using the same example as Section 6.6—the case where the second argument of the cons pattern for multisets is a wildcard.
matchAll dfs [1, 2, 3] (Multiset Something) [[mc| $x : _ -> x |]]
-- [1, 2, 3]The above matchAll expression is expanded as follows for wildcard optimization.
(\ (matcher, target) -> do
(x, _) <- cons (GP, WC) matcher target
let (_, _) = consM matcher target
return x)
(Multiset Something, [1, 2, 3])The cons function on line 2 takes a pattern-on-patterns as an additional first argument. The pattern-on-patterns distinguishes between wildcards and other patterns. Below, PP stands for Patterns for Patterns, WC for Wildcard, and GP for General Patterns.
data PP a = WC | GPThe cons function takes this pattern-on-patterns as an additional first argument. When the second argument of the cons pattern is a wildcard, it returns undefined as the next target for that second argument.
cons (GP, WC) (Multiset Something) [1, 2, 3]
-- [(1, undefined), (2, undefined), (3, undefined)]When the second argument of the cons pattern is not a wildcard, it computes and returns the collection as the next target.
cons (GP, GP) (Multiset Something) [1, 2, 3]
-- [(1, [2, 3]), (2, [1, 3]), (3, [1, 2])]8.3.2Pattern Fusion
Pattern fusion, the optimization explained in Section 6.5, cannot be added by users in Sweet Egison because Sweet Egison cannot perform pattern matching on patterns. Pattern fusion is defined as a built-in only for join-cons patterns, which frequently appear in pattern matching on lists. Sweet Egison transforms the join-cons pattern \(p_{1}\) ++ \(p_{2}\) : \(p_{3}\) into joinCons \(p_{1}\) \(p_{2}\) \(p_{3}\).
matchAll dfs [1, 2, 3] (List Something) [[mc| _ ++ $x : _ -> x |]]
-- [1, 2, 3]For example, the above matchAll expression is expanded as follows.
(\ (matcher, target) -> do
(_, x, _) <- joinCons (WC, GP, WC) matcher target
let (_, _, _) = joinConsM matcher target
(List Something, [1, 2, 3])8.4Types of Matchers and Patterns
The type of matchers is represented using a type class without class methods.
class Matcher m tgtUsing this type class, for example, the Something matcher is defined as follows. A type Something with data Something is defined, and an instance declaration expresses the relationship that data of type Something is a matcher for type a. Ideally, the data Something should be given a type like Matcher a directly, but this is not possible due to limitations of Haskell's type system.
data Something = Something
instance Matcher Something aAs described in Section 8.3, patterns are defined as functions that take a pattern-on-patterns, a matcher, and a target as arguments and return next targets.
type Pattern ps im it ot = ps -> im -> it -> [ot]To realize polymorphism of patterns, patterns are defined as functions belonging to a type class. For example, patterns for collections are defined using the following type class.
class CollectionPattern m t where
type ElemM m
type ElemT t
nil :: Pattern () m t ()
nilM :: m -> t -> ()
cons :: Pattern (PP (ElemT t), PP t) m t (ElemT t, t)
consM :: m -> t -> (ElemM m, m)
join :: Pattern (PP t, PP t) m t (t, t)
joinM :: m -> t -> (m, m)
joinCons :: Pattern (PP t, PP (ElemT t), PP t) m t (t, ElemT t, t)
joinConsM :: m -> t -> (m, ElemM m, m)8.5Matcher Definitions in Sweet Egison
The multiset matcher is defined as follows.
newtype Multiset m = Multiset m
instance Matcher m t => Matcher (Multiset m) [t]
instance Matcher m t => CollectionPattern (Multiset m) [t] where
type ElemM (Multiset m) = m
type ElemT [t] = t
cons (_, WC) (Multiset _) xs = map (\x -> (x, undefined)) xs
cons _ (Multiset _) xs = matchAll dfs xs (List Something)
[[mc| $hs ++ $x : $ts -> (x, hs ++ ts) |]]
consM (Multiset m) _ = (m, Multiset m)8.6User-Defined Search Strategies
A monad that can be used to describe search algorithms with backtracking is called a backtracking monad. The list monad is known as a representative backtracking monad. The list monad can be used to describe backtracking as follows. Here, the list monad is used to enumerate all pairs of integers from \(1\) to \(3\).
do ns <- [1..3]
x <- ns
y <- ns
return (x, y)
-- [(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)]The list monad searches the search tree in depth-first order. Therefore, when the search tree is infinitely large, it may not be able to enumerate all results.
do ns <- [1..]
x <- ns
y <- ns
return (x, y)
-- [(1,1),(1,2),(1,3),(1,4),(1,5),...]This raises the question of whether there exist corresponding monads for search strategies other than depth-first search, just as the list monad corresponds to depth-first search. Spivey discovered that for breadth-first search, a monad based on lists of lists as the underlying data structure corresponds [4]. This monad holds the nodes at depth \(n\) in the search tree in the \(n\)-th element list.
A backtracking monad has functions fromList and toList. These are conversion functions between the underlying data structure of the monad and lists. In the case of the depth-first search monad, since the underlying data structure is a list, both can be implemented as the id function. In the case of the breadth-first search monad, since the underlying data structure is a list of lists, the toList function becomes concat, and so on. For details on the implementation of backtracking monads, please refer to the Haskell library published on Hackage under the name backtracking [5].
Using backtracking monads, search strategies can be switched polymorphically. Below, dfs and bfs are functions for initializing the underlying data structures of the depth-first search and breadth-first search monads, respectively. By simply replacing dfs and bfs, the search strategy can be controlled.
toList (do
ns <- dfs [1..]
x <- fromList ns
y <- fromList ns
return (x, y))
-- [(1,1),(1,2),(1,3),(1,4),...]toList (do
ns <- bfs [1..]
x <- fromList ns
y <- fromList ns
return (x, y))
-- [(1,1),(1,2),(2,1),(1,3),...]What is passed as the first argument to matchAll is this initialization function for the monad of each search strategy.
matchAll strategy [1..] (Set Something) [[mc| $x : $y : _ -> (x, y) |]]By appropriately inserting this initialization function, fromList, and toList into the transformation result of matchAll, the search strategy can be controlled.
toList
((\ (matcher, target) -> do
(x, target') <- fromList (cons matcher target)
let (_, matcher') = consM matcher target
(y, _) <- fromList (cons matcher' target')
let (_, _) = consM matcher' target'
return (x, y))
(strategy (Set Something, [1..])))The monads for depth-first search and breadth-first search are defined in Haskell. Users can also add monads for new search strategies. This feature is unique to Sweet Egison and is not present in Egison itself.