-- 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
--   <a>http://reinerp.wordpress.com/category/pattern-combinators/</a> 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 <a>Data.Pattern</a>.
@package first-class-patterns
@version 0.3.2.4


-- | 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:
--   
--   <pre>
--   type instance Nil     :++: xs = xs
--   type instance (h:*:t) :++: xs = h :*: (t :++: xs)
--   </pre>


-- | Various types defined inductively as type families or data families on
--   type-lists.
module Data.Pattern.Base.Tuple

-- | Curried functions. We have
--   
--   <pre>
--   Fun '[x1, ..., xn] r   =   x1 -&gt; ... -&gt; xn -&gt; r
--   </pre>

-- | Tuples with types given by <tt>xs</tt>.
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 Data.Pattern.Base.Tuple.Distribute '[]
instance (Data.Pattern.Base.Tuple.Uncurriable t, Data.Pattern.Base.Tuple.Tupable t, Data.Pattern.Base.Tuple.Distribute t) => Data.Pattern.Base.Tuple.Distribute (h : t)
instance Data.Pattern.Base.Tuple.Tupable '[]
instance Data.Pattern.Base.Tuple.Tupable t => Data.Pattern.Base.Tuple.Tupable (h : t)
instance Data.Pattern.Base.Tuple.Uncurriable '[]
instance Data.Pattern.Base.Tuple.Uncurriable t => Data.Pattern.Base.Tuple.Uncurriable (h : t)


-- | The main types used in the implementation of first-class patterns:
--   <a>Pattern</a> and <a>Clause</a>.
module Data.Pattern.Base

-- | The pattern type. A value of type <tt>Pattern vars a</tt> is a pattern
--   which matches values of type <tt>a</tt> and binds variables with types
--   given by the type-list <tt>vars</tt>. For example, something of type
--   
--   <pre>
--   Pattern (a :*: c :*: Nil) (a,b,c)
--   </pre>
--   
--   is a pattern which matches against a triple and binds values of types
--   <tt>a</tt> and <tt>c</tt>. (A pattern of this type can be constructed
--   as <tt>tup3 var __ var</tt>.)
--   
--   Many "normal" patterns can be conveniently defined using <tt>mk0</tt>,
--   <tt>mk1</tt>, <tt>mk2</tt>, 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
--   
--   <pre>
--   pattern <a>-&gt;&gt;</a> function
--   </pre>
--   
--   where the function takes one argument for each variable bound by the
--   pattern.
--   
--   Clauses can be constructed with <tt>(<a>-&gt;&gt;</a>)</tt>, run with
--   <tt>tryMatch</tt>, and manipulated by the <a>Monad</a> and
--   <a>MonadPlus</a> instances. In particular, the
--   <tt>(<a>&lt;|&gt;</a>)</tt> operator from the <a>Alternative</a> class
--   is the way to list multiple cases in a pattern.
data Clause a r

-- | Extract the underlying computation constituting a <a>Clause</a>. This
--   function is not intended to be used directly; instead, see
--   <tt>match</tt>, <tt>tryMatch</tt>, <tt>mmatch</tt>, and <tt>elim</tt>
--   from <a>Data.Pattern.Common</a>.
runClause :: Clause a r -> ReaderT a Maybe r

-- | Construct a <a>Clause</a> from a pattern and a function which takes
--   one argument for each variable bound by the pattern. For example,
--   
--   <pre>
--   pair __ nothing     -&gt;&gt; 3
--   pair var nothing    -&gt;&gt; \x -&gt; x + 3
--   pair var (just var) -&gt;&gt; \x y -&gt; x + y + 3
--   </pre>
(->>) :: Pattern vars a -> Fun vars r -> Clause a r
infix 4 ->>

-- | An associative binary operation
(<|>) :: Alternative f => f a -> f a -> f a
infixl 3 <|>
instance GHC.Base.MonadPlus (Data.Pattern.Base.Clause a)
instance GHC.Base.Alternative (Data.Pattern.Base.Clause a)
instance GHC.Base.Monad (Data.Pattern.Base.Clause a)
instance GHC.Base.Applicative (Data.Pattern.Base.Clause a)
instance GHC.Base.Functor (Data.Pattern.Base.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

-- | <tt>give b</tt> always succeeds, ignoring the matched value and
--   providing the value <tt>b</tt> instead. Useful in conjunction with
--   <tt>(<a>/\</a>)</tt> 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.
--   
--   <tt>cst x = is (==x)</tt>.
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.
--   
--   <pre>
--   (/\) = <a>mk2</a> (\a -&gt; Just (a,a))
--   </pre>
(/\) :: 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 <a>view</a>.
(-->) :: (a -> b) -> Pattern vs b -> Pattern vs a
infix 5 -->

-- | 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 <a>tryView</a>.
(-?>) :: (a -> Maybe b) -> Pattern vs b -> Pattern vs a
infix 5 -?>

-- | Predicate pattern. Succeeds if the given predicate yields <a>True</a>,
--   fails otherwise.
--   
--   Can be used with <tt>(<a>/\</a>)</tt> for some uses similar to pattern
--   guards:
--   
--   <pre>
--   match a $
--        left (var /\ is even) -&gt;&gt; id
--    &lt;|&gt; left  __              -&gt;&gt; const 0
--    &lt;|&gt; right __              -&gt;&gt; const 1
--   </pre>
--   
--   Note that <a>is</a> is like <a>mk0</a> but with <a>Bool</a> instead of
--   <tt><a>Maybe</a> ()</tt>.
is :: (a -> Bool) -> Pattern '[] a

-- | <tt>pfilter p</tt> matches every element of a <a>Foldable</a> data
--   structure against the pattern <tt>p</tt>, 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)

-- | <tt>pmap p</tt> matches every element of a <a>Traversable</a> data
--   structure against the pattern <tt>p</tt>. The entire match fails if
--   any of the elements fail to match <tt>p</tt>. If all the elements
--   match, binds a <tt>t</tt>-structure full of bound values corresponding
--   to each variable bound in <tt>p</tt>.
pmap :: (Distribute vs, Traversable t) => Pattern vs a -> Pattern (Map t vs) (t a)

-- | <tt>pfoldr p f b</tt> matches every element of a <a>Foldable</a> data
--   structure against the pattern <tt>p</tt>, 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 <tt>pfilter
--   p</tt> and then appropriately combining and folding the resulting
--   lists of bound values. In particular, if <tt>p</tt> binds only one
--   value we have
--   
--   <pre>
--   match t (pfoldr p f b -&gt;&gt; id) === match t (pfilter p -&gt;&gt; foldr f b)
--   </pre>
--   
--   However, when <tt>p</tt> 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)

-- | <a>match</a> satisfies the identity <tt>match a c = fromJust (tryMatch
--   a c)</tt>.
match :: a -> Clause a r -> r

-- | "Runs" a <a>Clause</a>, by matching it against a value and returning a
--   result if it matches, or <tt>Nothing</tt> if the match fails.
tryMatch :: a -> Clause a r -> Maybe r

-- | <pre>
--   mmatch m p = m &gt;&gt;= <a>elim</a> p
--   </pre>
--   
--   Useful for applicative-looking monadic pattern matching, as in
--   
--   <pre>
--   ex7 :: IO ()
--   ex7 = mmatch getLine $
--         cst "" -&gt;&gt; return ()
--     &lt;|&gt; var    -&gt;&gt; putStrLn . ("You said " ++)
--   </pre>
mmatch :: (Monad m) => m a -> Clause a (m b) -> m b

-- | <pre>
--   elim = flip <a>match</a>
--   </pre>
--   
--   Useful for anonymous matching (or for building "eliminators", like
--   <a>maybe</a> and <a>either</a>). For example:
--   
--   <pre>
--   either withLeft withRight = elim $
--                left  var -&gt;&gt; withLeft
--            &lt;|&gt; right var -&gt;&gt; withRight
--   </pre>
elim :: Clause a r -> a -> r

-- | Match <tt>True</tt>.
true :: Pattern '[] Bool

-- | Match <tt>False</tt>.
false :: Pattern '[] Bool

-- | A strict match on the unit value <tt>()</tt>.
unit :: Pattern '[] ()

-- | A synonym for <a>unit</a>.
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 <a>pair</a>.
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 <a>Nothing</a> constructor of <a>Maybe</a>.
nothing :: Pattern '[] (Maybe a)

-- | Match the <a>Just</a> constructor of <a>Maybe</a>.
just :: Pattern vs a -> Pattern vs (Maybe a)

-- | Match the <a>Left</a> constructor of <a>Either</a>.
left :: Pattern vs a -> Pattern vs (Either a b)

-- | Match the <a>Right</a> constructor of <a>Either</a>.
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, <a>zero</a>
--   and <a>suc</a> allow viewing <tt>Integral</tt> types as Peano numbers.
--   
--   Note that <a>suc</a> 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 <a>Data.Pattern.Base</a>,
--   which defines the basic pattern type and some basic combinators. Then
--   read <a>Data.Pattern.Common</a>, which defines a number of convenient
--   combinators for constructing various sorts of patterns.
--   
--   As an example, the following functions, <tt>ex1</tt> and <tt>ex2</tt>,
--   are semantically equivalent:
--   
--   <pre>
--   ex1, ex2 :: Num a =&gt; Either a (a, a) -&gt; a
--   ex1 a = <a>match</a> a $
--             <a>left</a> (<a>cst</a> 4)         <a>-&gt;&gt;</a> 0
--         <a>&lt;|&gt;</a> <a>left</a> <a>var</a>             <a>-&gt;&gt;</a> id
--         <a>&lt;|&gt;</a> <a>right</a> (<a>tup2</a> <a>var</a> <a>var</a>) <a>-&gt;&gt;</a> (+)
--   ex2 a = case a of
--             Left 4      -&gt; 0
--             Left x      -&gt; x
--             Right (x,y) -&gt; x+y
--   </pre>
--   
--   Also, when optimisation is turned on, GHC will compile them to the
--   same code.
--   
--   XXX add more examples here.
module Data.Pattern
