Pattern matching is a convenient tool of programming languages that simplifies the description of data decomposition. Many pattern-match extensions have been developed for extending the range of data types to which pattern matching is applicable. Among them, the pattern-match system of the Egison programming language features practical pattern matching for non-free data types by providing a user-extensible non-linear pattern-match facility with backtracking.

This talk presents a Haskell library, Sweet Egison (https://github.com/egison/sweet-egison), that imports Egison’s non-deterministic pattern-match facility into Haskell. In this talk, we will present the user-interface and the implementation methods of Sweet Egison. We can regard pattern matching as syntactic sugar for representing non-determinism like list comprehensions.

• We will introduce the usage of Sweet Egison by showing several sample programs (https://github.com/egison/sweet-egison/blob/master/sample/).
• We will introduce our method of importing non-deterministic pattern matching. We transform non-deterministic patterns into a program that uses non-deterministic monads. We use Template Haskell for this transformation. This method makes the overhead for executing pattern matching small.

Finally, we would like to discuss implementing the proposed non-deterministic pattern-match facility as a GHC extension.