Haskell Language PatternSynonyms


Pattern synonyms are abstractions of patterns similar to how functions are abstractions of expressions.

For this example, let's look at the interface Data.Sequence exposes, and let's see how it can be improved with pattern synonyms. The Seq type is a data type that, internally, uses a complicated representation to achieve good asymptotic complexity for various operations, most notably both O(1) (un)consing and (un)snocing.

But this representation is unwieldy and some of its invariants cannot be expressed in Haskell's type system. Because of this, the Seq type is exposed to users as an abstract type, along with invariant-preserving accessor and constructor functions, among them:

empty :: Seq a

(<|) :: a -> Seq a -> Seq a
data ViewL a = EmptyL | a :< (Seq a)
viewl :: Seq a -> ViewL a

(|>) :: Seq a -> a -> Seq a 
data ViewR a = EmptyR | (Seq a) :> a 
viewr :: Seq a -> ViewR a

But using this interface can be a bit cumbersome:

uncons :: Seq a -> Maybe (a, Seq a)
uncons xs = case viewl xs of
    x :< xs' -> Just (x, xs')
    EmptyL -> Nothing

We can use view patterns to clean it up somewhat:

{-# LANGUAGE ViewPatterns #-}

uncons :: Seq a -> Maybe (a, Seq a)
uncons (viewl -> x :< xs) = Just (x, xs)
uncons _ = Nothing

Using the PatternSynonyms language extension, we can give an even nicer interface by allowing pattern matching to pretend that we have a cons- or a snoc-list:

{-# LANGUAGE PatternSynonyms #-}
import Data.Sequence (Seq)
import qualified Data.Sequence as Seq

pattern Empty :: Seq a
pattern Empty <- (Seq.viewl -> Seq.EmptyL)

pattern (:<) :: a -> Seq a -> Seq a
pattern x :< xs <- (Seq.viewl -> x Seq.:< xs)

pattern (:>) :: Seq a -> a -> Seq a
pattern xs :> x <- (Seq.viewr -> xs Seq.:> x)

This allows us to write uncons in a very natural style:

uncons :: Seq a -> Maybe (a, Seq a)
uncons (x :< xs) = Just (x, xs)
uncons _ = Nothing