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 Haskellanswer::SetInt->Stringanswer set =case member 42 set ofTrue->"We know the answer"False->"Never mind."-- Using view patternsanswer::SetInt->Stringanswer(member 42->True)="We know the answer"answer(member 42->False)="Never mind."`

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

`patternIsMember val <-(member val ->True)patternNotMember val <-(member val ->False)-- With extensionanswer::SetInt->Stringanswer(IsMember42)="We know the answer"answer(NotMember42)="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 HaskelladdressAlice::MapNameAddress->EitherStringAddressaddressAlice people =case lookup "Alice" people ofJust 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:

```
patternLookup key val <-(lookup key ->Just val)patternLookupFail key <-(lookup key ->Nothing)-- With extensionaddressAlice::MapNameAddress->EitherStringAddressaddressAlice(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::MapPerson(MapReceptacle(SetItems))->Statusfoo=\caseLookup"Bob"(LookupPocket(IsMemberKeys))->HasKeysLookup"Bob"(LookupPocket(NotMemberKeys))->NoKeysLookup"Bob"(LookupFailPocket)->NoPocketLookupFail"Bob"->Failure"No Bob"`

Another simple example is the `Between`

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

`importData.IxpatternBetween from to <-(inRange (from, to)->True)-- A teenager is between thirteen and nineteen.-- `Between 13 19` would be `13..19` in Rust.isTeen::Age->BoolisTeen(Between1319)=TrueisTeen_=False`

that gets transformed into:

`isTeen::Age->BoolisTeen(inRange (13,19)->True)=TrueisTeen_=False`

`Between`

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

):

`generalCategory'::Char->GeneralCategorygeneralCategory'=\caseBetween'\x00''\x16'->ControlBetween'a''z'->LowercaseLetterBetween'A''Z'->UppercaseLetterBetween'0''9'->DecimalNumber`

## Syntax

The syntax from PatternSynonyms can be reused for simplicity:

`patternLookup 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::MapStringInt->Intfn(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`

conid**varid.._{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 ofJust 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:

`moduleSet(Set, empty, insert, delete, has)wherenewtypeSet 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`

:

`patternHas x set <-(has x ->Just set)patternHasNot 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 bsbits::Int->ByteString->Maybe(Word,ByteString)`

and using the following pattern family:

`patternBits n val bs <-(bits n ->Just(val, bs))`

one can write a pattern like this:

`parsePacket::ByteString->_parsePacket(Bits3 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 =NothingpatternNP k n <-(np k ->Just n)
```

Used as follows:

```
fib::Num a -> a -> a
fib0=1fib1=1fib(NP2 n)= fib (n +1)+ fib n
```

Compare ViewPatternsAlternative version:

```
fib::Num a -> a -> a
fib0=1fib1=1fib(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(JustBoolT,Just ty2,Just ty3)->if ty2 = ty3
thenJust ty2
elseNothing_->Nothing
```

could be rewritten using pattern families as:

```
-- Here ‘Inf’ is a family indexed by ‘ctx’patternInf 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 ->JustBoolT)(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:

`patternMatch 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:

`importControl.Lens.PrismpatternMatch 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.0val= 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:

`patternGet i a <-(preview (nth i)->Just a)patternKey str a <-(preview (key str)->Just a)baz(Get0(Key"someObject"(Key"version"(Get1 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`