-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | First class patterns and pattern matching, using type families
--
-- This package implements a library of first class patterns. The initial
-- basis for this library was Morten Rhiger's "Type-safe pattern
-- combinators"; the patterns can be used in an almost identical way to
-- those of Morten Rhiger. In a series of blog posts at
-- http://reinerp.wordpress.com/category/pattern-combinators/ the
-- types of patterns were made more revealing using type families, and a
-- simpler implementation was used which avoids some book-keeping.
--
-- The library reimplements most of Haskell's built-in pattern matching
-- facilities, plus some more. The pattern matches of this library are
-- lightweight: when GHC's optimisation is turned on, all overhead should
-- be optimised away, leaving a standard Haskell pattern match.
--
-- If you're just reading the documentation for this library for the
-- first time, start with Data.Pattern.
@package first-class-patterns
@version 0.3.2
-- | Type-level lists. These lists only describe the types, but contain no
-- data. That is, they are phantom types.
module Data.Pattern.Base.TypeList
-- | Concatenation of lists. Instances:
--
--
-- type instance Nil :++: xs = xs
-- type instance (h:*:t) :++: xs = h :*: (t :++: xs)
--
-- | Various types defined inductively as type families or data families on
-- type-lists.
module Data.Pattern.Base.Tuple
-- | Curried functions. We have
--
--
-- Fun '[x1, ..., xn] r = x1 -> ... -> xn -> r
--
-- | Tuples with types given by xs.
data Tuple xs
-- | The empty tuple
zeroT :: Tuple '[]
-- | The singleton tuple
oneT :: a -> Tuple '[a]
-- | Concatenation of tuples.
(<>) :: Tuple xs -> Tuple ys -> Tuple (xs :++: ys)
-- | Runs a tuple by applying it to a curried function.
runTuple :: Tuple xs -> Fun xs r -> r
class Distribute xs
distribute :: (Distribute xs, Functor f) => f (Tuple xs) -> Tuple (Map f xs)
instance (Uncurriable t, Tupable t, Distribute t) => Distribute ((':) * h t)
instance Distribute ('[] *)
instance Tupable t => Tupable ((':) * h t)
instance Tupable ('[] *)
instance Uncurriable t => Uncurriable ((':) * h t)
instance Uncurriable ('[] *)
-- | The main types used in the implementation of first-class patterns:
-- Pattern and Clause.
module Data.Pattern.Base
-- | The pattern type. A value of type Pattern vars a is a pattern
-- which matches values of type a and binds variables with types
-- given by the type-list vars. For example, something of type
--
--
-- Pattern (a :*: c :*: Nil) (a,b,c)
--
--
-- is a pattern which matches against a triple and binds values of types
-- a and c. (A pattern of this type can be constructed
-- as tup3 var __ var.)
--
-- Many "normal" patterns can be conveniently defined using mk0,
-- mk1, mk2, and so on.
newtype Pattern vars a
Pattern :: (a -> Maybe (Tuple vars)) -> Pattern vars a
runPattern :: Pattern vars a -> a -> Maybe (Tuple vars)
-- | Pattern-match clauses. Typically something of the form
--
--
-- pattern ->> function
--
--
-- where the function takes one argument for each variable bound by the
-- pattern.
--
-- Clauses can be constructed with (->>), run with
-- tryMatch, and manipulated by the Monad and
-- MonadPlus instances. In particular, the
-- (<|>) operator from the Alternative class
-- is the way to list multiple cases in a pattern.
data Clause a r
-- | Extract the underlying computation constituting a Clause. This
-- function is not intended to be used directly; instead, see
-- match, tryMatch, mmatch, and elim
-- from Data.Pattern.Common.
runClause :: Clause a r -> ReaderT a Maybe r
-- | Construct a Clause from a pattern and a function which takes
-- one argument for each variable bound by the pattern. For example,
--
--
-- pair __ nothing ->> 3
-- pair var nothing ->> \x -> x + 3
-- pair var (just var) ->> \x y -> x + y + 3
--
(->>) :: Pattern vars a -> Fun vars r -> Clause a r
-- | An associative binary operation
(<|>) :: Alternative f => forall a. f a -> f a -> f a
instance Functor (Clause a)
instance Applicative (Clause a)
instance Monad (Clause a)
instance Alternative (Clause a)
instance MonadPlus (Clause a)
-- | A collection of useful pattern combinators.
module Data.Pattern.Common
-- | Variable pattern: always succeeds, and binds the value to a variable.
var :: Pattern '[a] a
-- | give b always succeeds, ignoring the matched value and
-- providing the value b instead. Useful in conjunction with
-- (/\) for providing default values in cases that would
-- otherwise not bind any values.
give :: b -> Pattern '[b] a
-- | Wildcard pattern: always succeeds, binding no variables. (This is
-- written as two underscores.)
__ :: Pattern '[] a
-- | Failure pattern: never succeeds.
pfail :: Pattern '[] a
-- | Constant pattern: test for equality to the given constant.
--
-- cst x = is (==x).
cst :: Eq a => a -> Pattern '[] a
-- | Conjunctive (and) pattern: matches a value against two patterns, and
-- succeeds only if both succeed, binding variables from both.
--
--
-- (/\) = mk2 (\a -> Just (a,a))
--
(/\) :: Pattern vs1 a -> Pattern vs2 a -> Pattern (vs1 :++: vs2) a
-- | Disjunctive (or) pattern: matches a value against the first pattern,
-- or against the second pattern if the first one fails.
(\/) :: Pattern as a -> Pattern as a -> Pattern as a
-- | View pattern: do some computation, then pattern match on the result.
view :: (a -> b) -> Pattern vs b -> Pattern vs a
-- | Convenient infix synonym for view.
(-->) :: (a -> b) -> Pattern vs b -> Pattern vs a
-- | Partial view pattern: do some (possibly failing) computation, then
-- pattern match on the result if the computation is successful.
tryView :: (a -> Maybe b) -> Pattern vs b -> Pattern vs a
-- | Convenient infix synonym for tryView.
(-?>) :: (a -> Maybe b) -> Pattern vs b -> Pattern vs a
-- | Predicate pattern. Succeeds if the given predicate yields True,
-- fails otherwise.
--
-- Can be used with (/\) for some uses similar to pattern
-- guards:
--
--
-- match a $
-- left (var /\ is even) ->> id
-- <|> left __ ->> const 0
-- <|> right __ ->> const 1
--
--
-- Note that is is like mk0 but with Bool instead of
-- Maybe ().
is :: (a -> Bool) -> Pattern '[] a
-- | pfilter p matches every element of a Foldable data
-- structure against the pattern p, discarding elements that do
-- not match. From the matching elements, binds a list of values
-- corresponding to each pattern variable.
pfilter :: (Distribute vs, Foldable t) => Pattern vs a -> Pattern (Map [] vs) (t a)
-- | pmap p matches every element of a Traversable data
-- structure against the pattern p. The entire match fails if
-- any of the elements fail to match p. If all the elements
-- match, binds a t-structure full of bound values corresponding
-- to each variable bound in p.
pmap :: (Distribute vs, Traversable t) => Pattern vs a -> Pattern (Map t vs) (t a)
-- | pfoldr p f b matches every element of a Foldable data
-- structure against the pattern p, discarding elements that do
-- not match. Folds over the bindings produced by the matching elements
-- to produce a summary value.
--
-- The same functionality could be achieved by matching with pfilter
-- p and then appropriately combining and folding the resulting
-- lists of bound values. In particular, if p binds only one
-- value we have
--
--
-- match t (pfoldr p f b ->> id) === match t (pfilter p ->> foldr f b)
--
--
-- However, when p binds more than one value, it can be
-- convenient to be able to process the bindings from each match
-- together, rather than having to deal with them once they are separated
-- out into separate lists.
pfoldr :: (Foldable t, Functor t) => Pattern vs a -> (Fun vs (b -> b)) -> b -> Pattern '[b] (t a)
-- | match satisfies the identity match a c = fromJust (tryMatch
-- a c).
match :: a -> Clause a r -> r
-- | "Runs" a Clause, by matching it against a value and returning a
-- result if it matches, or Nothing if the match fails.
tryMatch :: a -> Clause a r -> Maybe r
-- |
-- mmatch m p = m >>= elim p
--
--
-- Useful for applicative-looking monadic pattern matching, as in
--
--
-- ex7 :: IO ()
-- ex7 = mmatch getLine $
-- cst "" ->> return ()
-- <|> var ->> putStrLn . ("You said " ++)
--
mmatch :: Monad m => m a -> Clause a (m b) -> m b
-- |
-- elim = flip match
--
--
-- Useful for anonymous matching (or for building "eliminators", like
-- maybe and either). For example:
--
--
-- either withLeft withRight = elim $
-- left var ->> withLeft
-- <|> right var ->> withRight
--
elim :: Clause a r -> a -> r
-- | Match True.
true :: Pattern '[] Bool
-- | Match False.
false :: Pattern '[] Bool
-- | A strict match on the unit value ().
unit :: Pattern '[] ()
-- | A synonym for unit.
tup0 :: Pattern '[] ()
-- | Construct a pattern match against a pair from a pair of patterns.
pair :: Pattern vs1 a -> Pattern vs2 b -> Pattern (vs1 :++: vs2) (a, b)
-- | A synonym for pair.
tup2 :: Pattern vs1 a -> Pattern vs2 b -> Pattern (vs1 :++: vs2) (a, b)
-- | Match a 3-tuple.
tup3 :: Pattern vs1 a -> Pattern vs2 b -> Pattern vs3 c -> Pattern (vs1 :++: (vs2 :++: vs3)) (a, b, c)
-- | Match a 4-tuple.
tup4 :: Pattern vs1 a -> Pattern vs2 b -> Pattern vs3 c -> Pattern vs4 d -> Pattern (vs1 :++: (vs2 :++: (vs3 :++: vs4))) (a, b, c, d)
-- | Match a 5-tuple.
tup5 :: Pattern vs1 a -> Pattern vs2 b -> Pattern vs3 c -> Pattern vs4 d -> Pattern vs5 e -> Pattern (vs1 :++: (vs2 :++: (vs3 :++: (vs4 :++: vs5)))) (a, b, c, d, e)
-- | Match the Nothing constructor of Maybe.
nothing :: Pattern '[] (Maybe a)
-- | Match the Just constructor of Maybe.
just :: Pattern vs a -> Pattern vs (Maybe a)
-- | Match the Left constructor of Either.
left :: Pattern vs a -> Pattern vs (Either a b)
-- | Match the Right constructor of Either.
right :: Pattern vs b -> Pattern vs (Either a b)
-- | Match the empty list.
nil :: Pattern '[] [a]
-- | Match a cons.
cons :: Pattern vs1 a -> Pattern vs2 [a] -> Pattern (vs1 :++: vs2) [a]
-- | Match zero.
zero :: (Integral a, Eq a) => Pattern '[] a
-- | Match a natural number which is the successor of another natural (and
-- match the predecessor with a nested pattern). Together, zero
-- and suc allow viewing Integral types as Peano numbers.
--
-- Note that suc never matches negative numbers.
suc :: (Integral a, Eq a) => Pattern vs a -> Pattern vs a
mk0 :: (a -> Maybe ()) -> Pattern '[] a
mk1 :: (a -> Maybe b) -> Pattern vs b -> Pattern vs a
mk2 :: (a -> Maybe (b, c)) -> Pattern vs1 b -> Pattern vs2 c -> Pattern (vs1 :++: vs2) a
mk3 :: (a -> Maybe (b, c, d)) -> Pattern vs1 b -> Pattern vs2 c -> Pattern vs3 d -> Pattern (vs1 :++: (vs2 :++: vs3)) a
mk4 :: (a -> Maybe (b, c, d, e)) -> Pattern vs1 b -> Pattern vs2 c -> Pattern vs3 d -> Pattern vs4 e -> Pattern (vs1 :++: (vs2 :++: (vs3 :++: vs4))) a
mk5 :: (a -> Maybe (b, c, d, e, f)) -> Pattern vs1 b -> Pattern vs2 c -> Pattern vs3 d -> Pattern vs4 e -> Pattern vs5 f -> Pattern (vs1 :++: (vs2 :++: (vs3 :++: (vs4 :++: vs5)))) a
-- | The main module for first-class-patterns; to use the library it should
-- suffice to import this module. For a quick start using the library,
-- see the examples below.
--
-- If you want to read further, start with Data.Pattern.Base,
-- which defines the basic pattern type and some basic combinators. Then
-- read Data.Pattern.Common, which defines a number of convenient
-- combinators for constructing various sorts of patterns.
--
-- As an example, the following functions, ex1 and ex2,
-- are semantically equivalent:
--
--
-- ex1, ex2 :: Num a => Either a (a, a) -> a
-- ex1 a = match a $
-- left (cst 4) ->> 0
-- <|> left var ->> id
-- <|> right (tup2 var var) ->> (+)
-- ex2 a = case a of
-- Left 4 -> 0
-- Left x -> x
-- Right (x,y) -> x+y
--
--
-- Also, when optimisation is turned on, GHC will compile them to the
-- same code.
--
-- XXX add more examples here.
module Data.Pattern