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 do 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`