This is a proposal (formerly named *pattern families*) for extending pattern synonyms (PatternSynonyms) allowing patterns to depend on terms. The implementation is a straightforward desugaring into pattern synonyms and view patterns (ViewPatterns) so familiarity with those two extensions is recommended before reading the proposal.

The ticket associated with this design is #9671.

The simplest use case is checking whether a set contains a value:

-- Normal Haskell answer :: Set Int -> String answer set = case member 42 set of True -> "We know the answer" False -> "Never mind." -- Using view patterns answer :: Set Int -> String answer (member 42 -> True) = "We know the answer" answer (member 42 -> False) = "Never mind."

With this extension we could define patterns that check for containment:

pattern IsMember val <- (member val -> True) pattern NotMember val <- (member val -> False) -- With extension answer :: Set Int -> String answer (IsMember 42) = "We know the answer" answer (NotMember 42) = "Never mind."

This allows us to avoid pattern matching on the Boolean result of `member`

. In the case of `IsMember`

(and `NotMember`

) the argument `val`

flows into the view pattern as indicated by this figure:

Let's consider a similar example with a `Map`

where we want to look up a value based on some key:

-- Normal Haskell addressAlice :: Map Name Address -> Either String Address addressAlice people = case lookup "Alice" people of Just address -> Right address Nothing -> Left "Alice's address not found."

With the extension we define a pattern that only succeeds if `lookup`

returns a value wrapped in `Just`

which feeds that value back into the pattern:

pattern Lookup key val <- (lookup key -> Just val) pattern LookupFail key <- (lookup key -> Nothing) -- With extension addressAlice :: Map Name Address -> Either String Address addressAlice (Lookup "Alice" address) = Right address addressAlice _ = Left "Alice's address not found."

where the key `"Alice"`

is used in the view pattern expression and the resulting value is made available in the pattern main pattern:

Now we don't have to unnecessarily give a name to an argument (like `people`

) like with view patterns but unlike view patterns we don't need to mention to `Bool`

and `Maybe`

success result values of member and lookup. These kinds of patterns also nest arbitrarily without too much noise:

foo :: Map Person (Map Receptacle (Set Items)) -> Status foo = \case Lookup "Bob" (Lookup Pocket (IsMember Keys)) -> HasKeys Lookup "Bob" (Lookup Pocket (NotMember Keys)) -> NoKeys Lookup "Bob" (LookupFail Pocket) -> NoPocket LookupFail "Bob" -> Failure "No Bob"

Another simple example is the `Between`

pattern that matches a particular range (a feature built into Rust):

import Data.Ix pattern Between from to <- (inRange (from, to) -> True) -- A teenager is between thirteen and nineteen. -- `Between 13 19` would be `13..19` in Rust. isTeen :: Age -> Bool isTeen (Between 13 19) = True isTeen _ = False

that gets transformed into:

isTeen :: Age -> Bool isTeen (inRange (13, 19) -> True) = True isTeen _ = False

`Between`

will work on any indexable type (`Ix a => a`

):

generalCategory' :: Char -> GeneralCategory generalCategory' = \case Between '\x00' '\x16' -> Control Between 'a' 'z' -> LowercaseLetter Between 'A' 'Z' -> UppercaseLetter Between '0' '9' -> DecimalNumber

## Syntax

The syntax from PatternSynonyms can be reused for simplicity:

pattern Lookup key value <- (lookup key -> Just value)

here `value`

is a normal variable as in PatternSynonyms but `key`

is some term the view pattern is indexed by: this can be inferred from it appearing in the ViewPatterns expression (`lookup key`

) rather than in the pattern (`Just value`

).

The function `fn`

:

fn :: Map String Int -> Int fn (Lookup "five" n) = n

ghci> fn (Map.fromList [("four", 4), ("five", 5)] 5

is the same as writing `fn (lookup "five" -> Just n) = n`

using view patterns.

### Grammar

A simple grammar would then be

`pattern`

conidvarid.._{1}varid_{n}`<-`

(expr`->`

pat)

where each *varid _{i}* must be free in either

*expr*or

*pat*.

## Dynamic semantics (Desugaring)

More concretely, a pattern definition has the form:

`pattern`

conid[evarid,_{i}pvarid]_{j}`<-`

(expr`->`

pat)

where [*evarid _{i}*,

*pvarid*] denotes some interleaving of variables that appear in

_{j}*expr*or

*pat*. When matched against, all

*evarid*must be instantiated with expresions

_{i}*expr*:

_{i}

`fn`

(conid[expr,_{i}pvarid]) =_{j}`result`

where *pvarid _{j}* may appear in

`result`

as in usual patterns. This then gets translated into the following view pattern:

`fn`

(expr[evarid:=_{i}expr]_{i}`->`

`pat`

) =`result`

For the simple example of the pattern family `Take`

this (where 3 is *expr _{1}* and

`xs`

is *pval*):

_{1}foo (Lookup "five" n) = n + n

would get translated to:

foo (lookup "five" -> Just n) = n + n

which is the same as:

foo ys = case lookup "five" n of Just n -> n + n

## Static semantics (Typing)

If *expr* in the view pattern is an expression of type *t* with free variables *evarid _{i}* of type

*t*then an

_{i}*expr*used to instantiate the corresponding

_{i}*evarid*must have a type

_{i}*u*that unifies with

_{i}*t*, the final expression

_{i}*expr*will have type

*t*. Otherwise same typing and scoping rules as ViewPatterns.

## Motivating examples

### Sets

Example from ViewPatternsAlternative:

module Set(Set, empty, insert, delete, has) where newtype Set a = S [a] has :: Eq a => a -> Set a -> Maybe (Set a) has x (S xs) | x `elem` xs = Just (S (xs \\ [x])) | otherwise = Nothing

Using patterns indexed by an element of `Set a`

:

pattern Has x set <- (has x -> Just set) pattern HasNot x set <- (has x &&& id -> (Nothing, set))

One can write:

delete :: Eq a => a -> Set a -> Set a delete x (Has x set) = set delete x set = set insert :: Eq a => a -> Set a -> Set a insert x (HasNot x (S xs)) = S (x:xs) insert x set = set

Compare that to the the ViewPatternsAlternative proposal:

delete :: Eq a => a -> Set a -> Set a delete x (r | Just s <- has r) = set delete x set = set insert :: Eq a => a -> Set a -> Set a insert x (s | Just _ <- has x s) = set insert x (S xs) = S (x:xs)

Where the user has to worry about matching on `Just`

s.

### Erlang-style parsing

Another example stolen from ViewPatternsAlternative where the benefits are more apparent. Given a parsing function:

-- (bits n bs) parses n bits from the front of bs, returning -- the n-bit Word, and the remainder of bs bits :: Int -> ByteString -> Maybe (Word, ByteString)

and using the following pattern family:

pattern Bits n val bs <- (bits n -> Just (val, bs))

one can write a pattern like this:

parsePacket :: ByteString -> _ parsePacket (Bits 3 n (Bits n val bs)) = _

Where we can nest pattern families, more examples of nesting follow in the more advanced examples below. Compare that to the more verbose ViewPatternsAlternative version:

parsePacket :: ByteString -> _ parsePacket (p1 | Just (n, (p2 | Just (val, bs) <- bits n p2)) <- bits 3 p1) = _

### N+k patterns

Another one from ViewPatternsAlternative using the following view and pattern family:

np :: Num a => a -> a -> Maybe a np k n | k <= n = Just (n-k) | otherwise = Nothing pattern NP k n <- (np k -> Just n)

Used as follows:

fib :: Num a -> a -> a fib 0 = 1 fib 1 = 1 fib (NP 2 n) = fib (n + 1) + fib n

Compare ViewPatternsAlternative version:

fib :: Num a -> a -> a fib 0 = 1 fib 1 = 1 fib (n2 | let n = n2-2, n >= 0) = fib (n + 1) + fib n

### Type checking

From Bidirectional Typing Rules: A Tutorial:

inferType ctx (If t1 t2 t3) = case (inferType ctx t1, inferType ctx t2, inferType ctx t3) of (Just BoolT, Just ty2, Just ty3) -> if ty2 = ty3 then Just ty2 else Nothing _ -> Nothing

could be rewritten using pattern families as:

-- Here ‘Inf’ is a family indexed by ‘ctx’ pattern Inf ctx ty <- (inferType ctx -> Just ty) inferType ctx (If (Inf ctx BoolT) (Inf ctx ty1) (Inf ctx ty2)) | ty1 == ty2 = Just ty1 inferType ctx If{} = Nothing

allowing the user to pattern match *directly* on the inferable types without manually checking for `Just`

s — note the use of the previous argument `ctx`

to index later. This could currently be written somewhat awkwardly using view patterns:

inferType ctx (If (inferType ctx -> Just BoolT) (inferType ctx -> Just ty1) (inferType ctx -> Just ty2)) | ty1 == ty2 = Just ty1 inferType ctx If{} = Nothing

which is longer and clunkier, especially since the user is forced to deal with `Just`

s again.

Again one could use operators (`:⇒ = Inf`

) in which case it the examples follow notation in type theory more closely:

inferType γ (If (γ :⇒ BoolT) (γ :⇒ τ₁) (γ :⇒ τ₂)) = ...

### More advanced examples: Regular expressions

Given a regular expression operator `(~=) :: String -> String -> Maybe [String]`

we can define a pattern:

pattern Match x regexp <- ((~= regexp) -> Just x)

where `regexp`

is indexes the `Match`

pattern family:

firstWord (Match words "[a-zA-Z]+") = words firstWord _ = error "No words found"

or

vowels (Match vwls "[aeiou]") = length vwls

As an operator:

pattern x :~= regexp <- ((~= regexp) -> Just x)

### More advanced examples: Prism patterns

#### Matching a simple prism

Indexing patterns with prisms from Control.Lens.Prism:

import Control.Lens.Prism pattern Match prism a <- (preview prism -> Just a)

one can write

bar :: Either c (Either a b) -> a bar (Match (_Right._Left) a) = a bar _ = error "..."

#### More complicated prisms

Pattern families can be used to match nested data like JSON, ASTs or XML, here is an example of using it to match on Data.Aeson.Lens:

jsonBlob = "[{\"someObject\": {\"version\": [1,0,3]}}]" -- val = Number 0.0 val = jsonBlob ^?! nth 0 . key "someObject" . key "version" . nth 1

Pattern families allow us to say we want to fetch the same value as `val`

using patterns:

foo (Match (nth 0) (Match (key "someObject") (Match (key "version") (Match (nth 1) a)))) = a

Which is terribly verbose, but can be improved by introducing:

pattern Get i a <- (preview (nth i) -> Just a) pattern Key str a <- (preview (key str) -> Just a) baz (Get 0 (Key "someObject" (Key "version" (Get 1 a)))) = a

or by writing it infix:

baz (0 `Get` "someObject" `Key` "version" `Key` 1 `Get` a) = a

or by defining operators `:→ = Get i a`

and `:⇒ = Key`

:

baz (a :→ "someObject" :⇒ "version" :⇒ 1 :→ a) = a

### Attachments (2)

- member.png (10.0 KB) - added by 4 years ago.
- lookup.png (6.1 KB) - added by 4 years ago.

Download all attachments as: .zip