Version 23 (modified by 4 years ago) (diff)  ,

Pattern Synonyms
Most language entities in Haskell can be named so that they can be abbreviated instead of written out in full. This proposal provides the same power for patterns.
See the implementation page for implementation details.
Motivating example
Here is a simple representation of types
data Type = App String [Type]
Using this representations the arrow type looks like App ">" [t1, t2]
.
Here are functions that collect all argument types of nested arrows and recognize the Int
type:
collectArgs :: Type > [Type] collectArgs (App ">" [t1, t2]) = t1 : collectArgs t2 collectArgs _ = [] isInt (App "Int" []) = True isInt _ = False
Matching on App
directly is both hard to read and error prone to write.
The proposal is to introduce a way to give patterns names:
pattern Arrow t1 t2 = App ">" [t1, t2] pattern Int = App "Int" []
And now we can write
collectArgs :: Type > [Type] collectArgs (Arrow t1 t2) = t1 : collectArgs t2 collectArgs _ = [] isInt Int = True isInt _ = False
Here is a second example from pigworker on Reddit. Your basic sumsofproducts functors can be built from this kit.
newtype K a x = K a newtype I x = I x newtype (:+:) f g x = Sum (Either (f x) (g x)) newtype (:*:) f g x = Prod (f x, g x)
and then you can make recursive datatypes via
newtype Fix f = In (f (Fix f))
e.g.,
type Tree = Fix (K () :+: (I :*: I))
and you can get useful generic operations cheaply because the functors in the kit are all Traversable
, admit a partial zip operation, etc.
You can define friendly constructors for use in expressions
leaf :: Tree leaf = In (Sum (Left (K ()))) node :: Tree > Tree > Tree node l r = In (Sum (Right (Prod (I l, I r))))
but any Tree
specific pattern matching code you write will be wide and obscure. Turning these definitions into pattern synonyms means you can have both readable typespecific programs and handy generics without marshalling your data between views.
Unidirectional (patternonly) synonyms
The simplest form of pattern synonyms is the one from the examples above. The grammar rule is:
pattern
conid varid_{1} ... varid_{n} >
pat
pattern
varid_{1} consym varid_{2} >
pat
 Each of the variables on the left hand side must occur exactly once on the right hand side
 Pattern synonyms are not allowed to be recursive. Cf. type synonyms.
TODO 

There have been several proposals for the syntax of defining patternonly synonyms:

Pattern synonyms can be exported and imported by prefixing the conid with the keyword pattern
:
module Foo (pattern Arrow) where ...
This is required because pattern synonyms are in the namespace of constructors, so it's perfectly valid to have
data P = C pattern P = 42
You may also give a type signature for a pattern, but as with most other type signatures in Haskell it is optional:
pattern
conid ::
type
E.g.
pattern Arrow :: Type > Type > Type pattern Arrow t1 t2 > App ">" [t1, t2]
Together with ViewPatterns we can now create patterns that look like regular patterns to match on existing (perhaps abstract) types in new ways:
import qualified Data.Sequence as Seq pattern Empty > (Seq.viewl > Seq.EmptyL) pattern x :< xs > (Seq.viewl > x Seq.:< xs) pattern xs :> x > (Seq.viewr > xs Seq.:> x)
Simplybidirectional pattern synonyms
In cases where pat is in the intersection of the grammars for patterns and expressions (i.e. is valid both as an expression and a pattern), the pattern synonym can be made bidirectional, and can be used in expression contexts as well. Bidirectional pattern synonyms have the following syntax:
pattern
conid varid_{1} ... varid_{n} =
pat
pattern
varid_{1} consym varid_{2} =
pat
For example, the following two pattern synonym definitions are rejected, because they are not bidirectional (but they would be valid as patternonly synonyms)
pattern ThirdElem x = _:_:x:_ pattern Snd y = (x, y)
since the righthand side is not a closed expression of {x} and {y} respectively.
In contrast, the pattern synonyms for Arrow and Int above are bidirectional, so you can e.g. write:
arrows :: [Type] > Type > Type arrows = flip $ foldr Arrow
Explicitlybidirectional pattern synonyms
What if you want to use Succ
in an expression:
pattern Succ n > n1  let n = n1 1, n >= 0
It's clearly impossible since its expansion is a pattern that has no meaning as an expression. Nevertheless, if we want to make what looks like a constructor for a type we will often want to use it in both patterns and expressions. This is the rationale for the most complicated synonyms, the bidirectional ones. They provide two expansions, one for patterns and one for expressions.
pattern
conid varid_{1} ... varid_{n} >
pat where
cfunlhs rhs
where cfunlhs is like funlhs, except that the functions symbol is a conid instead of a varid.
Example:
pattern Succ n > n1  let n = n11, n >= 0 where Succ n = n + 1
TODO: Rewrite this example to not use ViewPatternsAlternative
The first part as is before and describes the expansion of the synonym in patterns. The second part describes the expansion in expressions.
fac 0 = 0 fac (Succ n) = Succ n * fac n
Associated pattern synonyms
Just like data types and type synonyms can be part of a class declaration, it would be possible to have pattern synonyms as well.
Example:
class ListLike l where pattern Nil :: l a pattern Cons :: a > l a > a isNil :: l a > Bool isNil Nil = True isNil (Cons _ _) = False append :: l a > l a > l a instance ListLike [] where pattern Nil = [] pattern Cons x xs = x:xs append = (++) headOf :: (ListLike l) => l a > Maybe a headOf Nil = Nothing headOf (Cons x _) = Just x
One could go one step further and leave out the pattern
keyword to obtain associated constructors, which are required to be bidirectional. The capitalized identifier would indicate that a pattern synonym is being defined. For complicated cases one could resort to the where
syntax (shown above).
TODO: Syntax for associated pattern synonym declarations to discern between patternonly and bidirectional pattern synonyms
Typed pattern synonyms
So far patterns only had syntactic meaning. In comparison Ωmega has typed pattern synonyms, so they become first class values. (I am not suggesting this for Haskell, yet.)
Semantics
It might seem tempting to just define pattern synonym semantics as 'textual substitution'. On the other hand, just like with any other surface language feature, we don't want to normalize away pattern synonyms before typechecking happens, since we want to report type error occurrences from userwritten code.
These two goals are incompatible once you start to factor in patterns containing typeclasspolymorphic parts. For example, let's say we have these two GADTs:
data S a where MkS:: Num a > a > S a data T a where MkT :: Eq a => a > T a
and we define this pattern synonym:
pattern P :: (Eq a, Num a) => a > a > (P a, S a) pattern P x y = (MkT x, MkS y)
we can then write a function:
f (P 1 2) = ...
which needs to use fromInteger
from the Num
instance provided by the MkS
constructor to be able to patternmatch on the argument of the MkT
constructor.
This means when we desugar a pattern synonym occurrence, the whole of the righthand side needs to be matched before the arguments are matched. So the previous definition of f
is desugared corresponding to the following Haskell code:
f = \a > case a of (MkT x, MkS y) > case x of 1 > case y of 2 > ...
Of course, we don't actually generate Haskell code for that; instead, the implementation directly emits Core, in the same way Core is emitted for other pattern matchings (in DsUtils.mkCoAlgCaseMatchResult
)