-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Dynamically-typed expressions involving applications and variables. -- -- Express is a library for manipulating dynamically typed Haskell -- expressions. It's like Data.Dynamic but with support for -- encoding applications and variables. -- -- It provides the Expr type and over a hundred functions for -- building, evaluating, comparing, folding, canonicalizing and matching -- Expr s. See the README and Haddock documentation for more -- details. @package express @version 0.1.3 -- | Re-exports the Data.List module along with additional functions -- over lists. module Data.Express.Utils.List -- | O(n log n). Sorts and remove repetitions. Equivalent to nub -- . sort. -- --

--   > nubSort [1,2,3]
--   [1,2,3]
--   > nubSort [3,2,1]
--   [1,2,3]
--   > nubSort [3,2,1,3,2,1]
--   [1,2,3]
--   > nubSort [3,3,1,1,2,2]
--   [1,2,3]
--

nubSort :: Ord a => [a] -> [a] nubSortBy :: (a -> a -> Ordering) -> [a] -> [a] -- | O(n log n). Checks that all elements of the first list are -- elements of the second. isPermutationOf :: Ord a => [a] -> [a] -> Bool -- | O(n log n). Checks that all elements of the first list are -- elements of the second. isSubsetOf :: Ord a => [a] -> [a] -> Bool -- | O(n log n). Checks that all elements are unique. This function -- is a faster equivalent to the following: -- --

--   isNub xs  =  nub xs == xs
--

-- -- Examples: -- --

--   isNub []       =  True
--   isNub [1,2,3]  =  True
--   isNub [2,1,2]  =  False
--

isNub :: Ord a => [a] -> Bool -- | O(n). Like lookup but returns the key itself if nothing -- is found. -- --

--   > lookupId 5 [(1,2),(3,4)]
--   5
--

-- --

--   > lookupId 5 [(1,2),(3,4),(5,6)]
--   6
--

lookupId :: Eq a => a -> [(a, a)] -> a (+++) :: Ord a => [a] -> [a] -> [a] infixr 5 +++ -- | Utilities for manipulating strings. -- -- At some point, this file was part of the Speculate tool. module Data.Express.Utils.String -- | Unquotes a string if possible, otherwise, this is just an identity. -- --

--   > unquote "\"string\""
--   "string"
--   > unquote "something else"
--   "something else"
--

unquote :: String -> String -- | Checks if a string-encoded Haskell expression is atomic. -- --

--   > atomic "123"
--   True
--   > atomic "42 + 1337"
--   False
--   > atomic "'a'"
--   True
--   > atomic "[1,2,3,4,5]"
--   True
--   > atomic "(1,2,3,4,5)"
--   True
--

-- -- FIXME: The current implementation may produce false positives: -- --

--   > atomic "'a' < 'b'"
--   True
--   > atomic "\"asdf\" ++ \"qwer\""
--   True
--   > atomic "[1,2,3] ++ [4,5,6]"
--   True
--

-- -- but this does not cause problems for (all?) most cases. atomic :: String -> Bool outernmostPrec :: String -> Maybe Int isNegativeLiteral :: String -> Bool -- | Check if a function / operator is infix -- --

--   isInfix "foo"   == False
--   isInfix "(+)"   == False
--   isInfix "`foo`" == True
--   isInfix "+"     == True
--

isInfix :: String -> Bool isPrefix :: String -> Bool -- | Is the string of the form `string` isInfixedPrefix :: String -> Bool -- | Transform an infix operator into an infix function: -- --

--   toPrefix "`foo`" == "foo"
--   toPrefix "+"     == "(+)"
--

toPrefix :: String -> String -- | Returns the precedence of default Haskell operators prec :: String -> Int -- | Returns an infinite list of variable names based on the given -- template. -- --

--   > variableNamesFromTemplate "x"
--   ["x", "y", "z", "x'", "y'", ...]
--

-- --

--   > variableNamesFromTemplate "p"
--   ["p", "q", "r", "p'", "q'", ...]
--

-- --

--   > variableNamesFromTemplate "xy"
--   ["xy", "zw", "xy'", "zw'", "xy''", ...]
--

variableNamesFromTemplate :: String -> [String] primeCycle :: [String] -> [String] -- | Defines the Name type class. module Data.Express.Name -- | If we were to come up with a variable name for the given type what -- name would it be? -- -- An instance for a given type Ty is simply given by: -- --

--   instance Name Ty where name _ = "x"
--

-- -- Examples: -- --

--   > name (undefined :: Int)
--   "x"
--

-- --

--   > name (undefined :: Bool)
--   "p"
--

-- --

--   > name (undefined :: [Int])
--   "xs"
--

-- -- This is then used to generate an infinite list of variable -- names: -- --

--   > names (undefined :: Int)
--   ["x", "y", "z", "x'", "y'", "z'", "x''", "y''", "z''", ...]
--

-- --

--   > names (undefined :: Bool)
--   ["p", "q", "r", "p'", "q'", "r'", "p''", "q''", "r''", ...]
--

-- --

--   > names (undefined :: [Int])
--   ["xs", "ys", "zs", "xs'", "ys'", "zs'", "xs''", "ys''", ...]
--

class Name a -- | O(1). -- -- Returns a name for a variable of the given argument's type. -- --

--   > name (undefined :: Int)
--   "x"
--

-- --

--   > name (undefined :: [Bool])
--   "ps"
--

-- --

--   > name (undefined :: [Maybe Integer])
--   "mxs"
--

-- -- The default definition is: -- --

--   name _ = "x"
--

name :: Name a => a -> String -- | Returns na infinite list of variable names from the given type: the -- result of variableNamesFromTemplate after name. -- --

--   > names (undefined :: Int)
--   ["x", "y", "z", "x'", "y'", "z'", "x''", "y''", "z''", ...]
--

-- --

--   > names (undefined :: Bool)
--   ["p", "q", "r", "p'", "q'", "r'", "p''", "q''", "r''", ...]
--

-- --

--   > names (undefined :: [Int])
--   ["xs", "ys", "zs", "xs'", "ys'", "zs'", "xs''", "ys''", ...]
--

names :: Name a => a -> [String] -- | Returns an infinite list of variable names based on the given -- template. -- --

--   > variableNamesFromTemplate "x"
--   ["x", "y", "z", "x'", "y'", ...]
--

-- --

--   > variableNamesFromTemplate "p"
--   ["p", "q", "r", "p'", "q'", ...]
--

-- --

--   > variableNamesFromTemplate "xy"
--   ["xy", "zw", "xy'", "zw'", "xy''", ...]
--

variableNamesFromTemplate :: String -> [String] instance Data.Express.Name.Name () instance Data.Express.Name.Name GHC.Types.Bool instance Data.Express.Name.Name GHC.Types.Int instance Data.Express.Name.Name GHC.Integer.Type.Integer instance Data.Express.Name.Name GHC.Types.Char instance Data.Express.Name.Name GHC.Types.Ordering instance Data.Express.Name.Name (GHC.Real.Ratio a) instance Data.Express.Name.Name GHC.Types.Float instance Data.Express.Name.Name GHC.Types.Double instance Data.Express.Name.Name (a -> b) instance Data.Express.Name.Name a => Data.Express.Name.Name (GHC.Maybe.Maybe a) instance (Data.Express.Name.Name a, Data.Express.Name.Name b) => Data.Express.Name.Name (Data.Either.Either a b) instance (Data.Express.Name.Name a, Data.Express.Name.Name b) => Data.Express.Name.Name (a, b) instance (Data.Express.Name.Name a, Data.Express.Name.Name b, Data.Express.Name.Name c) => Data.Express.Name.Name (a, b, c) instance (Data.Express.Name.Name a, Data.Express.Name.Name b, Data.Express.Name.Name c, Data.Express.Name.Name d) => Data.Express.Name.Name (a, b, c, d) instance Data.Express.Name.Name a => Data.Express.Name.Name [a] instance Data.Express.Name.Name GHC.Types.Word instance (Data.Express.Name.Name a, Data.Express.Name.Name b, Data.Express.Name.Name c, Data.Express.Name.Name d, Data.Express.Name.Name e) => Data.Express.Name.Name (a, b, c, d, e) instance (Data.Express.Name.Name a, Data.Express.Name.Name b, Data.Express.Name.Name c, Data.Express.Name.Name d, Data.Express.Name.Name e, Data.Express.Name.Name f) => Data.Express.Name.Name (a, b, c, d, e, f) instance (Data.Express.Name.Name a, Data.Express.Name.Name b, Data.Express.Name.Name c, Data.Express.Name.Name d, Data.Express.Name.Name e, Data.Express.Name.Name f, Data.Express.Name.Name g) => Data.Express.Name.Name (a, b, c, d, e, f, g) instance (Data.Express.Name.Name a, Data.Express.Name.Name b, Data.Express.Name.Name c, Data.Express.Name.Name d, Data.Express.Name.Name e, Data.Express.Name.Name f, Data.Express.Name.Name g, Data.Express.Name.Name h) => Data.Express.Name.Name (a, b, c, d, e, f, g, h) instance (Data.Express.Name.Name a, Data.Express.Name.Name b, Data.Express.Name.Name c, Data.Express.Name.Name d, Data.Express.Name.Name e, Data.Express.Name.Name f, Data.Express.Name.Name g, Data.Express.Name.Name h, Data.Express.Name.Name i) => Data.Express.Name.Name (a, b, c, d, e, f, g, h, i) instance (Data.Express.Name.Name a, Data.Express.Name.Name b, Data.Express.Name.Name c, Data.Express.Name.Name d, Data.Express.Name.Name e, Data.Express.Name.Name f, Data.Express.Name.Name g, Data.Express.Name.Name h, Data.Express.Name.Name i, Data.Express.Name.Name j) => Data.Express.Name.Name (a, b, c, d, e, f, g, h, i, j) instance (Data.Express.Name.Name a, Data.Express.Name.Name b, Data.Express.Name.Name c, Data.Express.Name.Name d, Data.Express.Name.Name e, Data.Express.Name.Name f, Data.Express.Name.Name g, Data.Express.Name.Name h, Data.Express.Name.Name i, Data.Express.Name.Name j, Data.Express.Name.Name k) => Data.Express.Name.Name (a, b, c, d, e, f, g, h, i, j, k) instance (Data.Express.Name.Name a, Data.Express.Name.Name b, Data.Express.Name.Name c, Data.Express.Name.Name d, Data.Express.Name.Name e, Data.Express.Name.Name f, Data.Express.Name.Name g, Data.Express.Name.Name h, Data.Express.Name.Name i, Data.Express.Name.Name j, Data.Express.Name.Name k, Data.Express.Name.Name l) => Data.Express.Name.Name (a, b, c, d, e, f, g, h, i, j, k, l) -- | Template Haskell utilities. module Data.Express.Utils.TH reallyDeriveCascading :: Name -> (Name -> DecsQ) -> Name -> DecsQ deriveWhenNeeded :: Name -> (Name -> DecsQ) -> Name -> DecsQ deriveWhenNeededOrWarn :: Name -> (Name -> DecsQ) -> Name -> DecsQ typeConArgs :: Name -> Q [Name] typeConArgsThat :: Name -> (Name -> Q Bool) -> Q [Name] typeConCascadingArgsThat :: Name -> (Name -> Q Bool) -> Q [Name] normalizeType :: Name -> Q (Type, [Type]) normalizeTypeUnits :: Name -> Q Type isInstanceOf :: Name -> Name -> Q Bool isntInstanceOf :: Name -> Name -> Q Bool -- | Given a type name, return the number of arguments taken by that type. -- Examples in partially broken TH: -- --

--   arity ''Int        === Q 0
--   arity ''Int->Int   === Q 0
--   arity ''Maybe      === Q 1
--   arity ''Either     === Q 2
--   arity ''Int->      === Q 1
--

-- -- This works for Data's and Newtype's and it is useful when generating -- typeclass instances. typeArity :: Name -> Q Int typeConstructors :: Name -> Q [(Name, [Type])] isTypeSynonym :: Name -> Q Bool typeSynonymType :: Name -> Q Type mergeIFns :: DecsQ -> DecsQ mergeI :: DecsQ -> DecsQ -> DecsQ lookupValN :: String -> Q Name showJustName :: Name -> String typeConstructorsArgNames :: Name -> Q [(Name, [Name])] (|=>|) :: Cxt -> DecsQ -> DecsQ (|++|) :: DecsQ -> DecsQ -> DecsQ whereI :: DecsQ -> [Dec] -> DecsQ -- | Allows automatic derivation of Name typeclass instances. module Data.Express.Name.Derive -- | Derives a Name instance for the given type Name. -- -- This function needs the TemplateHaskell extension. deriveName :: Name -> DecsQ -- | Derives a Name instance for a given type Name cascading -- derivation of type arguments as well. deriveNameCascading :: Name -> DecsQ -- | Same as deriveName but does not warn when instance already -- exists (deriveName is preferable). deriveNameIfNeeded :: Name -> DecsQ -- | This module is part of Express. -- -- Utilities to manipulate TypeReps (of Typeable values). module Data.Express.Utils.Typeable tyArity :: TypeRep -> Int unFunTy :: TypeRep -> (TypeRep, TypeRep) isFunTy :: TypeRep -> Bool argumentTy :: TypeRep -> TypeRep resultTy :: TypeRep -> TypeRep finalResultTy :: TypeRep -> TypeRep boolTy :: TypeRep intTy :: TypeRep orderingTy :: TypeRep mkComparisonTy :: TypeRep -> TypeRep mkCompareTy :: TypeRep -> TypeRep funTyCon :: TyCon compareTy :: TypeRep -> TypeRep -> Ordering -- | This function returns the type of the element of a list. It will throw -- an error when not given the list type. -- --

--   > > elementTy $ typeOf (undefined :: [Int])
--   Int
--   > > elementTy $ typeOf (undefined :: [[Int]])
--   [Int]
--   > > elementTy $ typeOf (undefined :: [Bool])
--   Bool
--   > > elementTy $ typeOf (undefined :: Bool)
--   *** Exception: error (elementTy): `Bool' is not a list type
--

elementTy :: TypeRep -> TypeRep -- | O(n). Return all sub types of a given type including itself. -- --

--   > typesIn $ typeOf (undefined :: Int)
--   [Int]
--

-- --

--   > typesIn $ typeOf (undefined :: Bool)
--   [Bool]
--

-- --

--   > typesIn $ typeOf (undefined :: [Int])
--   [ Int
--   , [Int]
--   ]
--

-- --

--   > typesIn $ typeOf (undefined :: Int -> Int -> Int)
--   [ Int
--   , Int -> Int
--   , Int -> Int -> Int
--   ]
--

-- --

--   > typesIn $ typeOf (undefined :: Int -> [Int] -> [Int])
--   [ Int
--   , [Int]
--   , [Int] -> [Int]
--   , Int -> [Int] -> [Int]
--   ]
--

-- --

--   > typesIn $ typeOf (undefined :: Maybe Bool)
--   [ Bool
--   , Maybe Bool
--   ]
--

typesIn :: TypeRep -> [TypeRep] typesInList :: [TypeRep] -> [TypeRep] -- | An infix alias for mkFunTy. It is right associative. (->::) :: TypeRep -> TypeRep -> TypeRep infixr 9 ->:: -- | This module defines the Expr type and basic utilities involving -- it. -- -- This is the core of the Express library. As a user, you are probably -- better of importing Data.Express. If you want to understand how -- the library works, this is the place to start. -- -- The complexity of most functions are given in big O notation where -- n is the size of the expression being manipulated or produced. -- There may still be a m cost associated with the values being -- stored in Exprs. module Data.Express.Core -- | Values of type Expr represent objects or applications between -- objects. Each object is encapsulated together with its type and string -- representation. Values encoded in Exprs are always monomorphic. -- -- An Expr can be constructed using: -- --

val, for values that are Show instances;
value, for values that are not Show instances, like -- functions;
:$, for applications between Exprs.

-- --

--   > val False
--   False :: Bool
--

-- --

--   > value "not" not :$ val False
--   not False :: Bool
--

-- -- An Expr can be evaluated using evaluate, eval or -- evl. -- --

--   > evl $ val (1 :: Int) :: Int
--   1
--

-- --

--   > evaluate $ val (1 :: Int) :: Maybe Bool
--   Nothing
--

-- --

--   > eval 'a' (val 'b')
--   'b'
--

-- -- Showing a value of type Expr will return a -- pretty-printed representation of the expression together with its -- type. -- --

--   > show (value "not" not :$ val False)
--   "not False :: Bool"
--

-- -- Expr is like Dynamic but has support for applications -- and variables (:$, var). -- -- The var underscore convention: Functions that manipulate -- Exprs usually follow the convention where a value whose -- String representation starts with '_' represents a -- variable. data Expr -- | a value enconded as String and Dynamic Value :: String -> Dynamic -> Expr -- | function application between expressions (:$) :: Expr -> Expr -> Expr -- | O(1). It takes a string representation of a value and a value, -- returning an Expr with that terminal value. For instances of -- Show, it is preferable to use val. -- --

--   > value "0" (0 :: Integer)
--   0 :: Integer
--

-- --

--   > value "'a'" 'a'
--   'a' :: Char
--

-- --

--   > value "True" True
--   True :: Bool
--

-- --

--   > value "id" (id :: Int -> Int)
--   id :: Int -> Int
--

-- --

--   > value "(+)" ((+) :: Int -> Int -> Int)
--   (+) :: Int -> Int -> Int
--

-- --

--   > value "sort" (sort :: [Bool] -> [Bool])
--   sort :: [Bool] -> [Bool]
--

value :: Typeable a => String -> a -> Expr -- | O(1). A shorthand for value for values that are -- Show instances. -- --

--   > val (0 :: Int)
--   0 :: Int
--

-- --

--   > val 'a'
--   'a' :: Char
--

-- --

--   > val True
--   True :: Bool
--

-- -- Example equivalences to value: -- --

--   val 0     =  value "0" 0
--   val 'a'   =  value "'a'" 'a'
--   val True  =  value "True" True
--

val :: (Typeable a, Show a) => a -> Expr -- | O(n). Creates an Expr representing a function -- application. Just an Expr application if the types -- match, Nothing otherwise. (cf. :$) -- --

--   > value "id" (id :: () -> ()) $$ val ()
--   Just (id () :: ())
--

-- --

--   > value "abs" (abs :: Int -> Int) $$ val (1337 :: Int)
--   Just (abs 1337 :: Int)
--

-- --

--   > value "abs" (abs :: Int -> Int) $$ val 'a'
--   Nothing
--

-- --

--   > value "abs" (abs :: Int -> Int) $$ val ()
--   Nothing
--

($$) :: Expr -> Expr -> Maybe Expr -- | O(1). Creates an Expr representing a variable with the -- given name and argument type. -- --

--   > var "x" (undefined :: Int)
--   x :: Int
--

-- --

--   > var "u" (undefined :: ())
--   u :: ()
--

-- --

--   > var "xs" (undefined :: [Int])
--   xs :: [Int]
--

-- -- This function follows the underscore convention: a variable is -- just a value whose string representation starts with underscore -- ('_'). var :: Typeable a => String -> a -> Expr -- | O(n). Just the value of an expression when possible -- (correct type), Nothing otherwise. This does not catch errors -- from undefined Dynamic values. -- --

--   > let one = val (1 :: Int)
--   > let bee = val 'b'
--   > let negateE = value "negate" (negate :: Int -> Int)
--

-- --

--   > evaluate one :: Maybe Int
--   Just 1
--

-- --

--   > evaluate one :: Maybe Char
--   Nothing
--

-- --

--   > evaluate bee :: Maybe Int
--   Nothing
--

-- --

--   > evaluate bee :: Maybe Char
--   Just 'b'
--

-- --

--   > evaluate $ negateE :$ one :: Maybe Int
--   Just (-1)
--

-- --

--   > evaluate $ negateE :$ bee :: Maybe Int
--   Nothing
--

evaluate :: Typeable a => Expr -> Maybe a -- | O(n). Evaluates an expression when possible (correct type). -- Returns a default value otherwise. -- --

--   > let two = val (2 :: Int)
--   > let three = val (3 :: Int)
--   > let e1 -+- e2 = value "+" ((+) :: Int->Int->Int) :$ e1 :$ e2
--

-- --

--   > eval 0 $ two -+- three :: Int
--   5
--

-- --

--   > eval 'z' $ two -+- three :: Char
--   'z'
--

-- --

--   > eval 0 $ two -+- val '3' :: Int
--   0
--

eval :: Typeable a => a -> Expr -> a -- | O(n). Evaluates an expression when possible (correct type). -- Raises an error otherwise. -- --

--   > evl $ two -+- three :: Int
--   5
--

-- --

--   > evl $ two -+- three :: Bool
--   *** Exception: evl: cannot evaluate Expr `2 + 3 :: Int' at the Bool type
--

-- -- This may raise errors, please consider using eval or -- evaluate. evl :: Typeable a => Expr -> a -- | O(n). Computes the type of an expression. This raises errors, -- but this should not happen if expressions are smart-constructed. -- --

--   > let one = val (1 :: Int)
--   > let bee = val 'b'
--   > let absE = value "abs" (abs :: Int -> Int)
--

-- --

--   > typ one
--   Int
--

-- --

--   > typ bee
--   Char
--

-- --

--   > typ absE
--   Int -> Int
--

-- --

--   > typ (absE :$ one)
--   Int
--

-- --

--   > typ (absE :$ bee)
--   *** Exception: type mismatch, cannot apply `Int -> Int' to `Char'
--

-- --

--   > typ ((absE :$ bee) :$ one)
--   *** Exception: type mismatch, cannot apply `Int -> Int' to `Char'
--

typ :: Expr -> TypeRep -- | O(n). Computes the type of an expression returning either the -- type of the given expression when possible or when there is a type -- error, the pair of types which produced the error. -- --

--   > let one = val (1 :: Int)
--   > let bee = val 'b'
--   > let absE = value "abs" (abs :: Int -> Int)
--

-- --

--   > etyp one
--   Right Int
--

-- --

--   > etyp bee
--   Right Char
--

-- --

--   > etyp absE
--   Right (Int -> Int)
--

-- --

--   > etyp (absE :$ one)
--   Right Int
--

-- --

--   > etyp (absE :$ bee)
--   Left (Int -> Int, Char)
--

-- --

--   > etyp ((absE :$ bee) :$ one)
--   Left (Int -> Int, Char)
--

etyp :: Expr -> Either (TypeRep, TypeRep) TypeRep -- | O(n). Returns Just the type of an expression or -- Nothing when there is an error. -- --

--   > let one = val (1 :: Int)
--   > let bee = val 'b'
--   > let absE = value "abs" (abs :: Int -> Int)
--

-- --

--   > mtyp one
--   Just Int
--

-- --

--   > mtyp (absE :$ bee)
--   Nothing
--

mtyp :: Expr -> Maybe TypeRep -- | O(n). Evaluates an expression to a terminal Dynamic -- value when possible. Returns Nothing otherwise. -- --

--   > toDynamic $ val (123 :: Int) :: Maybe Dynamic
--   Just <<Int>>
--

-- --

--   > toDynamic $ value "abs" (abs :: Int -> Int) :$ val (-1 :: Int)
--   Just <<Int>>
--

-- --

--   > toDynamic $ value "abs" (abs :: Int -> Int) :$ val 'a'
--   Nothing
--

toDynamic :: Expr -> Maybe Dynamic -- | O(1). Returns whether an Expr is a terminal value -- (Value). -- --

--   > isValue $ var "x" (undefined :: Int)
--   True
--

-- --

--   > isValue $ val False
--   True
--

-- --

--   > isValue $ value "not" not :$ var "p" (undefined :: Bool)
--   False
--

-- -- This is equivalent to pattern matching the Value constructor. -- -- Properties: -- --

```
 isValue (Value e) = True
```
```
 isValue (e1 :$ e2) = False
```
```
 isValue = not . isApp
```
```
 isValue e = isVar e || isConst e
```

isValue :: Expr -> Bool -- | O(1). Returns whether an Expr is an application -- (:$). -- --

--   > isApp $ var "x" (undefined :: Int)
--   False
--

-- --

--   > isApp $ val False
--   False
--

-- --

--   > isApp $ value "not" not :$ var "p" (undefined :: Bool)
--   True 
--

-- -- This is equivalent to pattern matching the :$ constructor. -- -- Properties: -- --

```
 isApp (e1 :$ e2) = True
```
```
 isApp (Value e) = False
```
```
 isApp = not . isValue
```

 isApp e = not (isVar e) && not (isConst
--   e)

isApp :: Expr -> Bool -- | O(1). Returns whether an Expr is a terminal variable -- (var). (cf. hasVar). -- --

--   > isVar $ var "x" (undefined :: Int)
--   True
--

-- --

--   > isVar $ val False
--   False
--

-- --

--   > isVar $ value "not" not :$ var "p" (undefined :: Bool)
--   False
--

isVar :: Expr -> Bool -- | O(1). Returns whether an Expr is a terminal constant. -- (cf. isGround). -- --

--   > isConst $ var "x" (undefined :: Int)
--   False
--

-- --

--   > isConst $ val False
--   True
--

-- --

--   > isConst $ value "not" not :$ val False
--   False
--

isConst :: Expr -> Bool -- | O(n). Returns whether the given Expr is ill typed. (cf. -- isWellTyped) -- --

--   > let one = val (1 :: Int)
--   > let bee = val 'b'
--   > let absE = value "abs" (abs :: Int -> Int)
--

-- --

--   > isIllTyped (absE :$ val (1 :: Int))
--   False
--

-- --

--   > isIllTyped (absE :$ val 'b')
--   True
--

isIllTyped :: Expr -> Bool -- | O(n). Returns whether the given Expr is well typed. (cf. -- isIllTyped) -- --

--   > isWellTyped (absE :$ val (1 :: Int))
--   True
--

-- --

--   > isWellTyped (absE :$ val 'b')
--   False
--

isWellTyped :: Expr -> Bool -- | O(n). Check if an Expr has a variable. (By convention, -- any value whose String representation starts with -- '_'.) -- --

--   > hasVar $ value "not" not :$ val True
--   False
--

-- --

--   > hasVar $ value "&&" (&&) :$ var "p" (undefined :: Bool) :$ val True
--   True
--

hasVar :: Expr -> Bool -- | O(n). Returns whether a Expr has no variables. -- This is equivalent to "not . hasVar". -- -- The name "ground" comes from term rewriting. -- --

--   > isGround $ value "not" not :$ val True
--   True
--

-- --

--   > isGround $ value "&&" (&&) :$ var "p" (undefined :: Bool) :$ val True
--   False
--

isGround :: Expr -> Bool -- | O(n). Compares the complexity of two Exprs. An -- expression e1 is strictly simpler than another -- expression e2 if the first of the following conditions to -- distingish between them is: -- --

e1 is smaller in size/length than e2, e.g.: x + -- y < x + (y + z);
or, e1 has more distinct variables than e2, e.g.: -- x + y < x + x;
or, e1 has more variable occurrences than e2, e.g.: -- x + x < 1 + x;
or, e1 has fewer distinct constants than e2, e.g.: -- 1 + 1 < 0 + 1.

-- -- They're otherwise considered of equal complexity, e.g.: x + y -- and y + z. -- --

--   > (xx -+- yy) `compareComplexity` (xx -+- (yy -+- zz))
--   LT
--

-- --

--   > (xx -+- yy) `compareComplexity` (xx -+- xx)
--   LT
--

-- --

--   > (xx -+- xx) `compareComplexity` (one -+- xx)
--   LT
--

-- --

--   > (one -+- one) `compareComplexity` (zero -+- one)
--   LT
--

-- --

--   > (xx -+- yy) `compareComplexity` (yy -+- zz)
--   EQ
--

-- --

--   > (zero -+- one) `compareComplexity` (one -+- zero)
--   EQ
--

compareComplexity :: Expr -> Expr -> Ordering -- | O(n). Return the arity of the given expression, i.e. the number -- of arguments that its type takes. -- --

--   > arity (val (0::Int))
--   0
--

-- --

--   > arity (val False)
--   0
--

-- --

--   > arity (value "id" (id :: Int -> Int))
--   1
--

-- --

--   > arity (value "const" (const :: Int -> Int -> Int))
--   2
--

-- --

--   > arity (one -+- two)
--   0
--

arity :: Expr -> Int -- | O(n). Returns the size of the given expression, i.e. the number -- of terminal values in it. -- --

--   zero       =  val (0 :: Int)
--   one        =  val (1 :: Int)
--   two        =  val (2 :: Int)
--   xx -+- yy  =  value "+" ((+) :: Int->Int->Int) :$ xx :$ yy
--   abs' xx    =  value "abs" (abs :: Int->Int) :$ xx
--

-- --

--   > size zero
--   1
--

-- --

--   > size (one -+- two)
--   3
--

-- --

--   > size (abs' one)
--   2
--

size :: Expr -> Int -- | O(n). Returns the maximum depth of a given expression given by -- the maximum number of nested function applications. Curried function -- application is counted only once, i.e. the application of a two -- argument function increases the depth of both its arguments by one. -- (cf. height) -- -- With -- --

--   zero       =  val (0 :: Int)
--   one        =  val (1 :: Int)
--   two        =  val (2 :: Int)
--   xx -+- yy  =  value "+" ((+) :: Int->Int->Int) :$ xx :$ yy
--   abs' xx    =  value "abs" (abs :: Int->Int) :$ xx
--

-- --

--   > depth zero
--   1
--

-- --

--   > depth (one -+- two)
--   2
--

-- --

--   > depth (abs' one -+- two)
--   3
--

-- -- Flipping arguments of applications in any of the subterms does not -- affect the result. depth :: Expr -> Int -- | O(n). Returns the maximum height of a given expression given by -- the maximum number of nested function applications. Curried function -- application is counted each time, i.e. the application of a two -- argument function increases the depth of its first argument by two and -- of its second argument by one. (cf. depth) -- -- With: -- --

--   zero          =  val (0 :: Int)
--   one           =  val (1 :: Int)
--   two           =  val (2 :: Int)
--   const' xx yy  =  value "const" (const :: Int->Int->Int) :$ xx :$ yy
--   abs' xx       =  value "abs" (abs :: Int->Int) :$ xx
--

-- -- Then: -- --

--   > height zero
--   1
--

-- --

--   > height (abs' one)
--   2
--

-- --

--   > height ((const' one) two)
--   3
--

-- --

--   > height ((const' (abs' one)) two)
--   4
--

-- --

--   > height ((const' one) (abs' two))
--   3
--

-- -- Flipping arguments of applications in subterms may change the result -- of the function. height :: Expr -> Int -- | O(n) for the spine, O(n^2) for full evaluation. Lists -- subexpressions of a given expression in order and with repetitions. -- This includes the expression itself and partial function applications. -- (cf. nubSubexprs) -- --

--   > subexprs (xx -+- yy)
--   [ x + y :: Int
--   , (x +) :: Int -> Int
--   , (+) :: Int -> Int -> Int
--   , x :: Int
--   , y :: Int
--   ]
--

-- --

--   > subexprs (pp -&&- (pp -&&- true))
--   [ p && (p && True) :: Bool
--   , (p &&) :: Bool -> Bool
--   , (&&) :: Bool -> Bool -> Bool
--   , p :: Bool
--   , p && True :: Bool
--   , (p &&) :: Bool -> Bool
--   , (&&) :: Bool -> Bool -> Bool
--   , p :: Bool
--   , True :: Bool
--   ]
--

subexprs :: Expr -> [Expr] -- | O(n). Lists all terminal values in an expression in order and -- with repetitions. (cf. nubValues) -- --

--   > values (xx -+- yy)
--   [ (+) :: Int -> Int -> Int
--   , x :: Int
--   , y :: Int
--   ]
--

-- --

--   > values (xx -+- (yy -+- zz))
--   [ (+) :: Int -> Int -> Int
--   , x :: Int
--   , (+) :: Int -> Int -> Int
--   , y :: Int
--   , z :: Int
--   ]
--

-- --

--   > values (zero -+- (one -*- two))
--   [ (+) :: Int -> Int -> Int
--   , 0 :: Int
--   , (*) :: Int -> Int -> Int
--   , 1 :: Int
--   , 2 :: Int
--   ]
--

-- --

--   > values (pp -&&- true)
--   [ (&&) :: Bool -> Bool -> Bool
--   , p :: Bool
--   , True :: Bool
--   ]
--

values :: Expr -> [Expr] -- | O(n). Lists all variables in an expression in order and with -- repetitions. (cf. nubVars) -- --

--   > vars (xx -+- yy)
--   [ x :: Int
--   , y :: Int
--   ]
--

-- --

--   > vars (xx -+- (yy -+- xx))
--   [ x :: Int
--   , y :: Int
--   , x :: Int
--   ]
--

-- --

--   > vars (zero -+- (one -*- two))
--   []
--

-- --

--   > vars (pp -&&- true)
--   [p :: Bool]
--

vars :: Expr -> [Expr] -- | O(n). List terminal constants in an expression in order and -- with repetitions. (cf. nubConsts) -- --

--   > consts (xx -+- yy)
--   [ (+) :: Int -> Int -> Int ]
--

-- --

--   > consts (xx -+- (yy -+- zz))
--   [ (+) :: Int -> Int -> Int
--   , (+) :: Int -> Int -> Int
--   ]
--

-- --

--   > consts (zero -+- (one -*- two))
--   [ (+) :: Int -> Int -> Int
--   , 0 :: Int
--   , (*) :: Int -> Int -> Int
--   , 1 :: Int
--   , 2 :: Int
--   ]
--

-- --

--   > consts (pp -&&- true)
--   [ (&&) :: Bool -> Bool -> Bool
--   , True :: Bool
--   ]
--

consts :: Expr -> [Expr] -- | O(n log n) for the spine, O(n^2) for full evaluation. -- Lists all subexpressions of a given expression without repetitions. -- This includes the expression itself and partial function applications. -- (cf. subexprs) -- --

--   > nubSubexprs (xx -+- yy)
--   [ x :: Int
--   , y :: Int
--   , (+) :: Int -> Int -> Int
--   , (x +) :: Int -> Int
--   , x + y :: Int
--   ]
--

-- --

--   > nubSubexprs (pp -&&- (pp -&&- true))
--   [ p :: Bool
--   , True :: Bool
--   , (&&) :: Bool -> Bool -> Bool
--   , (p &&) :: Bool -> Bool
--   , p && True :: Bool
--   , p && (p && True) :: Bool
--   ]
--

nubSubexprs :: Expr -> [Expr] -- | O(n log n). Lists all terminal values in an expression without -- repetitions. (cf. values) -- --

--   > nubValues (xx -+- yy)
--   [ x :: Int
--   , y :: Int
--   , (+) :: Int -> Int -> Int
--

-- -- ] -- --

--   > nubValues (xx -+- (yy -+- zz))
--   [ x :: Int
--   , y :: Int
--   , z :: Int
--   , (+) :: Int -> Int -> Int
--   ]
--

-- --

--   > nubValues (zero -+- (one -*- two))
--   [ 0 :: Int
--   , 1 :: Int
--   , 2 :: Int
--   , (*) :: Int -> Int -> Int
--   , (+) :: Int -> Int -> Int
--   ]
--

-- --

--   > nubValues (pp -&&- pp)
--   [ p :: Bool
--   , (&&) :: Bool -> Bool -> Bool
--   ]
--

nubValues :: Expr -> [Expr] -- | O(n log n). Lists all variables in an expression without -- repetitions. (cf. vars) -- --

--   > nubVars (yy -+- xx)
--   [ x :: Int
--   , y :: Int
--   ]
--

-- --

--   > nubVars (xx -+- (yy -+- xx))
--   [ x :: Int
--   , y :: Int
--   ]
--

-- --

--   > nubVars (zero -+- (one -*- two))
--   []
--

-- --

--   > nubVars (pp -&&- true)
--   [p :: Bool]
--

nubVars :: Expr -> [Expr] -- | O(n log n). List terminal constants in an expression without -- repetitions. (cf. consts) -- --

--   > nubConsts (xx -+- yy)
--   [ (+) :: Int -> Int -> Int ]
--

-- --

--   > nubConsts (xx -+- (yy -+- zz))
--   [ (+) :: Int -> Int -> Int ]
--

-- --

--   > nubConsts (pp -&&- true)
--   [ True :: Bool
--   , (&&) :: Bool -> Bool -> Bool
--   ]
--

nubConsts :: Expr -> [Expr] -- | O(n). Unfold a function application Expr into a list of -- function and arguments. -- --

--   unfoldApp $ e0                    =  [e0]
--   unfoldApp $ e0 :$ e1              =  [e0,e1]
--   unfoldApp $ e0 :$ e1 :$ e2        =  [e0,e1,e2]
--   unfoldApp $ e0 :$ e1 :$ e2 :$ e3  =  [e0,e1,e2,e3]
--

-- -- Remember :$ is left-associative, so: -- --

--   unfoldApp e0                          =  [e0]
--   unfoldApp (e0 :$ e1)                  =  [e0,e1]
--   unfoldApp ((e0 :$ e1) :$ e2)          =  [e0,e1,e2]
--   unfoldApp (((e0 :$ e1) :$ e2) :$ e3)  =  [e0,e1,e2,e3]
--

unfoldApp :: Expr -> [Expr] -- | O(n). Returns a string representation of an expression. -- Differently from show (:: Expr -> String) this -- function does not include the type in the output. -- --

--   > putStrLn $ showExpr (one -+- two)
--   1 + 2
--

-- --

--   > putStrLn $ showExpr $ (pp -||- true) -&&- (qq -||- false)
--   (p || True) && (q || False)
--

showExpr :: Expr -> String showOpExpr :: String -> Expr -> String showPrecExpr :: Int -> Expr -> String instance GHC.Show.Show Data.Express.Core.Expr instance GHC.Classes.Eq Data.Express.Core.Expr instance GHC.Classes.Ord Data.Express.Core.Expr -- | Utilities for mapping or transforming Exprs. module Data.Express.Map -- | O(n*m). Applies a function to all terminal values in an -- expression. (cf. //-) -- -- Given that: -- --

--   > let zero  = val (0 :: Int)
--   > let one   = val (1 :: Int)
--   > let two   = val (2 :: Int)
--   > let three = val (3 :: Int)
--   > let xx -+- yy = value "+" ((+) :: Int->Int->Int) :$ xx :$ yy
--   > let intToZero e = if typ e == typ zero then zero else e
--

-- -- Then: -- --

--   > one -+- (two -+- three)
--   1 + (2 + 3) :: Int
--

-- --

--   > mapValues intToZero $ one -+- (two -+- three)
--   0 + (0 + 0) :: Integer
--

-- -- Given that the argument function is O(m), this function is -- O(n*m). mapValues :: (Expr -> Expr) -> Expr -> Expr -- | O(n*m). Applies a function to all variables in an expression. -- -- Given that: -- --

--   > let primeify e = if isVar e
--   |                  then case e of (Value n d) -> Value (n ++ "'") d
--   |                  else e
--   > let xx = var "x" (undefined :: Int)
--   > let yy = var "y" (undefined :: Int)
--   > let xx -+- yy = value "+" ((+) :: Int->Int->Int) :$ xx :$ yy
--

-- -- Then: -- --

--   > xx -+- yy
--   x + y :: Int
--

-- --

--   > primeify xx
--   x' :: Int
--

-- --

--   > mapVars primeify $ xx -+- yy
--   x' + y' :: Int
--

-- --

--   > mapVars (primeify . primeify) $ xx -+- yy
--   x'' + y'' :: Int
--

-- -- Given that the argument function is O(m), this function is -- O(n*m). mapVars :: (Expr -> Expr) -> Expr -> Expr -- | O(n*m). Applies a function to all terminal constants in an -- expression. -- -- Given that: -- --

--   > let one   = val (1 :: Int)
--   > let two   = val (2 :: Int)
--   > let xx -+- yy = value "+" ((+) :: Int->Int->Int) :$ xx :$ yy
--   > let intToZero e = if typ e == typ zero then zero else e
--

-- -- Then: -- --

--   > one -+- (two -+- xx)
--   1 + (2 + x) :: Int
--

-- --

--   > mapConsts intToZero (one -+- (two -+- xx))
--   0 + (0 + x) :: Integer
--

-- -- Given that the argument function is O(m), this function is -- O(n*m). mapConsts :: (Expr -> Expr) -> Expr -> Expr -- | O(n*m). Substitute subexpressions of an expression using the -- given function. Outer expressions have more precedence than inner -- expressions. (cf. //) -- -- With: -- --

--   > let xx = var "x" (undefined :: Int)
--   > let yy = var "y" (undefined :: Int)
--   > let zz = var "z" (undefined :: Int)
--   > let plus = value "+" ((+) :: Int->Int->Int)
--   > let times = value "*" ((*) :: Int->Int->Int)
--   > let xx -+- yy = plus :$ xx :$ yy
--   > let xx -*- yy = times :$ xx :$ yy
--

-- --

--   > let pluswap (o :$ xx :$ yy) | o == plus = Just $ o :$ yy :$ xx
--   |     pluswap _                           = Nothing
--

-- -- Then: -- --

--   > mapSubexprs pluswap $ (xx -*- yy) -+- (yy -*- zz)
--   y * z + x * y :: Int
--

-- --

--   > mapSubexprs pluswap $ (xx -+- yy) -*- (yy -+- zz)
--   (y + x) * (z + y) :: Int
--

-- -- Substitutions do not stack, in other words a replaced expression or -- its subexpressions are not further replaced: -- --

--   > mapSubexprs pluswap $ (xx -+- yy) -+- (yy -+- zz)
--   (y + z) + (x + y) :: Int
--

-- -- Given that the argument function is O(m), this function is -- O(n*m). mapSubexprs :: (Expr -> Maybe Expr) -> Expr -> Expr -- | O(n*m). Substitute occurrences of values in an expression from -- the given list of substitutions. (cf. mapValues) -- -- Given that: -- --

--   > let xx = var "x" (undefined :: Int)
--   > let yy = var "y" (undefined :: Int)
--   > let zz = var "z" (undefined :: Int)
--   > let xx -+- yy = value "+" ((+) :: Int->Int->Int) :$ xx :$ yy
--

-- -- Then: -- --

--   > ((xx -+- yy) -+- (yy -+- zz)) //- [(xx, yy), (zz, yy)]
--   (y + y) + (y + y) :: Int
--

-- --

--   > ((xx -+- yy) -+- (yy -+- zz)) //- [(yy, yy -+- zz)]
--   (x + (y + z)) + ((y + z) + z) :: Int
--

-- -- This function does not work for substituting non-terminal -- subexpressions: -- --

--   > (xx -+- yy) //- [(xx -+- yy, zz)]
--   x + y :: Int
--

-- -- Please use the slower // if you want the above replacement to -- work. -- -- Replacement happens only once: -- --

--   > xx //- [(xx,yy), (yy,zz)]
--   y :: Int
--

-- -- Given that the argument list has length m, this function is -- O(n*m). (//-) :: Expr -> [(Expr, Expr)] -> Expr -- | O(n*n*m). Substitute subexpressions in an expression from the -- given list of substitutions. (cf. mapSubexprs). -- -- Please consider using //- if you are replacing just terminal -- values as it is faster. -- -- Given that: -- --

--   > let xx = var "x" (undefined :: Int)
--   > let yy = var "y" (undefined :: Int)
--   > let zz = var "z" (undefined :: Int)
--   > let xx -+- yy = value "+" ((+) :: Int->Int->Int) :$ xx :$ yy
--

-- -- Then: -- --

--   > ((xx -+- yy) -+- (yy -+- zz)) // [(xx -+- yy, yy), (yy -+- zz, yy)]
--   y + y :: Int
--

-- --

--   > ((xx -+- yy) -+- zz) // [(xx -+- yy, zz), (zz, xx -+- yy)]
--   z + (x + y) :: Int
--

-- -- Replacement happens only once with outer expressions having more -- precedence than inner expressions. -- --

--   > (xx -+- yy) // [(yy,xx), (xx -+- yy,zz), (zz,xx)]
--   z :: Int
--

-- -- Given that the argument list has length m, this function is -- O(n*n*m). Remember that since n is the size of an -- expression, comparing two expressions is O(n) in the worst -- case, and we may need to compare with n subexpressions in the -- worst case. (//) :: Expr -> [(Expr, Expr)] -> Expr -- | Rename variables in an Expr. -- --

--   > renameVarsBy (++ "'") (xx -+- yy)
--   x' + y' :: Int
--

-- --

--   > renameVarsBy (++ "'") (yy -+- (zz -+- xx))
--   (y' + (z' + x')) :: Int
--

-- --

--   > renameVarsBy (++ "1") (abs' xx)
--   abs x1 :: Int
--

-- --

--   > renameVarsBy (++ "2") $ abs' (xx -+- yy)
--   abs (x2 + y2) :: Int
--

-- -- NOTE: this will affect holes! renameVarsBy :: (String -> String) -> Expr -> Expr -- | Utilities for manipulating variables and typed holes encoded as -- Exprs. module Data.Express.Hole -- | O(1). Creates a variable with the same type as the given -- Expr. -- --

--   > let one = val (1::Int)
--   > "x" `varAsTypeOf` one
--   x :: Int
--

-- --

--   > "p" `varAsTypeOf` val False
--   p :: Bool
--

varAsTypeOf :: String -> Expr -> Expr -- | Generate an infinite list of variables based on a template and a given -- type. (cf. listVarsAsTypeOf) -- --

--   > putL 10 $ listVars "x" (undefined :: Int)
--   [ x :: Int
--   , y :: Int
--   , z :: Int
--   , x' :: Int
--   , y' :: Int
--   , z' :: Int
--   , x'' :: Int
--   , ...
--   ]
--

-- --

--   > putL 10 $ listVars "p" (undefined :: Bool)
--   [ p :: Bool
--   , q :: Bool
--   , r :: Bool
--   , p' :: Bool
--   , q' :: Bool
--   , r' :: Bool
--   , p'' :: Bool
--   , ...
--   ]
--

listVars :: Typeable a => String -> a -> [Expr] -- | Generate an infinite list of variables based on a template and the -- type of a given Expr. (cf. listVars) -- --

--   > let one = val (1::Int)
--   > putL 10 $ "x" `listVarsAsTypeOf` one
--   [ x :: Int
--   , y :: Int
--   , z :: Int
--   , x' :: Int
--   , ...
--   ]
--

-- --

--   > let false = val False
--   > putL 10 $ "p" `listVarsAsTypeOf` false
--   [ p :: Bool
--   , q :: Bool
--   , r :: Bool
--   , p' :: Bool
--   , ...
--   ]
--

listVarsAsTypeOf :: String -> Expr -> [Expr] -- | O(1). Creates an Expr representing a typed hole of the -- given argument type. -- --

--   > hole (undefined :: Int)
--   _ :: Int
--

-- --

--   > hole (undefined :: Maybe String)
--   _ :: Maybe [Char]
--

-- -- A hole is represented as a variable with no name or a value named -- "_": -- --

--   hole x = var "" x
--   hole x = value "_" x
--

hole :: Typeable a => a -> Expr -- | O(1). Checks if an Expr represents a typed hole. (cf. -- hole) -- --

--   > isHole $ hole (undefined :: Int)
--   True
--

-- --

--   > isHole $ value "not" not :$ val True
--   False
--

-- --

--   > isHole $ val 'a'
--   False
--

isHole :: Expr -> Bool -- | O(n). Lists all holes in an expression, in order and with -- repetitions. (cf. nubHoles) -- --

--   > holes $ hole (undefined :: Bool)
--   [_ :: Bool]
--

-- --

--   > holes $ value "&&" (&&) :$ hole (undefined :: Bool) :$ hole (undefined :: Bool)
--   [_ :: Bool,_ :: Bool]
--

-- --

--   > holes $ hole (undefined :: Bool->Bool) :$ hole (undefined::Bool)
--   [_ :: Bool -> Bool,_ :: Bool]
--

holes :: Expr -> [Expr] -- | O(n log n). Lists all holes in an expression without -- repetitions. (cf. holes) -- --

--   > nubHoles $ hole (undefined :: Bool)
--   [_ :: Bool]
--

-- --

--   > nubHoles $ value "&&" (&&) :$ hole (undefined :: Bool) :$ hole (undefined :: Bool)
--   [_ :: Bool]
--

-- --

--   > nubHoles $ hole (undefined :: Bool->Bool) :$ hole (undefined::Bool)
--   [_ :: Bool,_ :: Bool -> Bool]
--

nubHoles :: Expr -> [Expr] -- | O(1). Creates an Expr representing a typed hole with the -- type of the given Expr. (cf. hole) -- --

--   > val (1::Int)
--   1 :: Int
--   > holeAsTypeOf $ val (1::Int)
--   _ :: Int
--

holeAsTypeOf :: Expr -> Expr -- | Defines utilities for folding and unfolding Exprs. module Data.Express.Fold -- | O(n). Folds a list of Exprs into a single Expr. -- (cf. unfold) -- -- This always generates an ill-typed expression. -- --

--   fold [val False, val True, val (1::Int)]
--   [False,True,1] :: ill-typed # ExprList $ Bool #
--

-- -- This is useful when applying transformations on lists of Exprs, -- such as canonicalize, mapValues or -- canonicalVariations. -- --

--   > let ii = var "i" (undefined::Int)
--   > let kk = var "k" (undefined::Int)
--   > let qq = var "q" (undefined::Bool)
--   > let notE = value "not" not
--   > unfold . canonicalize . fold $ [ii,kk,notE :$ qq, notE :$ val False]
--   [x :: Int,y :: Int,not p :: Bool,not False :: Bool]
--

fold :: [Expr] -> Expr -- | O(n). Unfolds an Expr representing a list into a list of -- Exprs. This reverses the effect of fold. -- --

--   > expr [1,2,3::Int]
--   [1,2,3] :: [Int]
--   > unfold $ expr [1,2,3::Int]
--   [1 :: Int,2 :: Int,3 :: Int]
--

unfold :: Expr -> [Expr] -- | O(1). Folds a pair of Expr values into a single -- Expr. (cf. unfoldPair) -- -- This always generates an ill-typed expression. -- --

--   > foldPair (val False, val (1::Int))
--   (False,1) :: ill-typed # ExprPair $ Bool #
--

-- --

--   > foldPair (val (0::Int), val True)
--   (0,True) :: ill-typed # ExprPair $ Int #
--

-- -- This is useful when applying transformations on pairs of Exprs, -- such as canonicalize, mapValues or -- canonicalVariations. -- --

--   > let ii = var "i" (undefined::Int)
--   > let kk = var "k" (undefined::Int)
--   > unfoldPair $ canonicalize $ foldPair (ii,kk)
--   (x :: Int,y :: Int)
--

foldPair :: (Expr, Expr) -> Expr -- | O(1). Unfolds an Expr representing a pair. This reverses -- the effect of foldPair. -- --

--   > value "," ((,) :: Bool->Bool->(Bool,Bool)) :$ val True :$ val False
--   (True,False) :: (Bool,Bool)
--   > unfoldPair $ value "," ((,) :: Bool->Bool->(Bool,Bool)) :$ val True :$ val False
--   (True :: Bool,False :: Bool)
--

unfoldPair :: Expr -> (Expr, Expr) foldTrio :: (Expr, Expr, Expr) -> Expr unfoldTrio :: Expr -> (Expr, Expr, Expr) -- | O(n). Folds a list of Expr with function application -- (:$). This reverses the effect of unfoldApp. -- --

--   foldApp [e0]           =  e0
--   foldApp [e0,e1]        =  e0 :$ e1
--   foldApp [e0,e1,e2]     =  e0 :$ e1 :$ e2
--   foldApp [e0,e1,e2,e3]  =  e0 :$ e1 :$ e2 :$ e3
--

-- -- Remember :$ is left-associative, so: -- --

--   foldApp [e0]           =    e0
--   foldApp [e0,e1]        =   (e0 :$ e1)
--   foldApp [e0,e1,e2]     =  ((e0 :$ e1) :$ e2)
--   foldApp [e0,e1,e2,e3]  = (((e0 :$ e1) :$ e2) :$ e3)
--

-- -- This function may produce an ill-typed expression. foldApp :: [Expr] -> Expr -- | O(n). Unfold a function application Expr into a list of -- function and arguments. -- --

--   unfoldApp $ e0                    =  [e0]
--   unfoldApp $ e0 :$ e1              =  [e0,e1]
--   unfoldApp $ e0 :$ e1 :$ e2        =  [e0,e1,e2]
--   unfoldApp $ e0 :$ e1 :$ e2 :$ e3  =  [e0,e1,e2,e3]
--

-- -- Remember :$ is left-associative, so: -- --

--   unfoldApp e0                          =  [e0]
--   unfoldApp (e0 :$ e1)                  =  [e0,e1]
--   unfoldApp ((e0 :$ e1) :$ e2)          =  [e0,e1,e2]
--   unfoldApp (((e0 :$ e1) :$ e2) :$ e3)  =  [e0,e1,e2,e3]
--

unfoldApp :: Expr -> [Expr] -- | Defines the Express type class. module Data.Express.Express -- | Express typeclass instances provide an expr function -- that allows values to be deeply encoded as applications of -- Exprs. -- --

--   expr False  =  val False
--   expr (Just True)  =  value "Just" (Just :: Bool -> Maybe Bool) :$ val True
--

-- -- The function expr can be contrasted with the function -- val: -- --

val always encodes values as atomic Value -- Exprs -- shallow encoding.
expr ideally encodes expressions as applications -- (:$) between Value Exprs -- deep encoding.

-- -- Depending on the situation, one or the other may be desirable. -- -- Instances can be automatically derived using the TH function -- deriveExpress. -- -- The following example shows a datatype and its instance: -- --

--   data Stack a = Stack a (Stack a) | Empty
--

-- --

--   instance Express a => Express (Stack a) where
--     expr s@(Stack x y) = value "Stack" (Stack ->>: s) :$ expr x :$ expr y
--     expr s@Empty       = value "Empty" (Empty   -: s)
--

-- -- To declare expr it may be useful to use auxiliary type binding -- operators: -:, ->:, ->>:, -- ->>>:, ->>>>:, -- ->>>>>:, ... -- -- For types with atomic values, just declare expr = val class Typeable a => Express a expr :: Express a => a -> Expr -- | Type restricted version of const that forces its first argument to -- have the same type as the second. -- --

--   value -: (undefined :: Ty)  =  value :: Ty
--

(-:) :: a -> a -> a infixl 1 -: -- | Type restricted version of const that forces the result of its first -- argument to have the same type as the second. -- --

--   f ->: (undefined :: Ty)  =  f :: a -> Ty
--

(->:) :: (a -> b) -> b -> a -> b infixl 1 ->: -- | Type restricted version of const that forces the result of the result -- of its first argument to have the same type as the second. -- --

--   f ->>: (undefined :: Ty)  =  f :: a -> b -> Ty
--

(->>:) :: (a -> b -> c) -> c -> a -> b -> c infixl 1 ->>: -- | Type restricted version of const that forces the result of the result -- of the result of its first argument to have the same type as the -- second. (->>>:) :: (a -> b -> c -> d) -> d -> a -> b -> c -> d infixl 1 ->>>: -- | Forces the result type of a 4-argument function. (->>>>:) :: (a -> b -> c -> d -> e) -> e -> a -> b -> c -> d -> e infixl 1 ->>>>: -- | Forces the result type of a 5-argument function. (->>>>>:) :: (a -> b -> c -> d -> e -> f) -> f -> a -> b -> c -> d -> e -> f infixl 1 ->>>>>: -- | Forces the result type of a 6-argument function. (->>>>>>:) :: (a -> b -> c -> d -> e -> f -> g) -> g -> a -> b -> c -> d -> e -> f -> g infixl 1 ->>>>>>: -- | Forces the result type of a 7-argument function. (->>>>>>>:) :: (a -> b -> c -> d -> e -> f -> g -> h) -> h -> a -> b -> c -> d -> e -> f -> g -> h infixl 1 ->>>>>>>: -- | Forces the result type of a 8-argument function. (->>>>>>>>:) :: (a -> b -> c -> d -> e -> f -> g -> h -> i) -> i -> a -> b -> c -> d -> e -> f -> g -> h -> i infixl 1 ->>>>>>>>: -- | Forces the result type of a 9-argument function. (->>>>>>>>>:) :: (a -> b -> c -> d -> e -> f -> g -> h -> i -> j) -> j -> a -> b -> c -> d -> e -> f -> g -> h -> i -> j infixl 1 ->>>>>>>>>: -- | Forces the result type of a 10-argument function. (->>>>>>>>>>:) :: (a -> b -> c -> d -> e -> f -> g -> h -> i -> j -> k) -> k -> a -> b -> c -> d -> e -> f -> g -> h -> i -> j -> k infixl 1 ->>>>>>>>>>: -- | Forces the result type of a 11-argument function. (->>>>>>>>>>>:) :: (a -> b -> c -> d -> e -> f -> g -> h -> i -> j -> k -> l) -> l -> a -> b -> c -> d -> e -> f -> g -> h -> i -> j -> k -> l infixl 1 ->>>>>>>>>>>: -- | Forces the result type of a 12-argument function. (->>>>>>>>>>>>:) :: (a -> b -> c -> d -> e -> f -> g -> h -> i -> j -> k -> l -> m) -> m -> a -> b -> c -> d -> e -> f -> g -> h -> i -> j -> k -> l -> m infixl 1 ->>>>>>>>>>>>: instance Data.Express.Express.Express () instance Data.Express.Express.Express GHC.Types.Bool instance Data.Express.Express.Express GHC.Types.Int instance Data.Express.Express.Express GHC.Integer.Type.Integer instance Data.Express.Express.Express GHC.Types.Char instance Data.Express.Express.Express GHC.Types.Ordering instance Data.Express.Express.Express a => Data.Express.Express.Express (GHC.Maybe.Maybe a) instance (Data.Express.Express.Express a, Data.Express.Express.Express b) => Data.Express.Express.Express (Data.Either.Either a b) instance (Data.Express.Express.Express a, Data.Express.Express.Express b) => Data.Express.Express.Express (a, b) instance (Data.Express.Express.Express a, Data.Express.Express.Express b, Data.Express.Express.Express c) => Data.Express.Express.Express (a, b, c) instance (Data.Express.Express.Express a, Data.Express.Express.Express b, Data.Express.Express.Express c, Data.Express.Express.Express d) => Data.Express.Express.Express (a, b, c, d) instance Data.Express.Express.Express a => Data.Express.Express.Express [a] instance (GHC.Real.Integral a, GHC.Show.Show a, Data.Express.Express.Express a) => Data.Express.Express.Express (GHC.Real.Ratio a) instance (Data.Express.Express.Express a, Data.Express.Express.Express b, Data.Express.Express.Express c, Data.Express.Express.Express d, Data.Express.Express.Express e) => Data.Express.Express.Express (a, b, c, d, e) instance (Data.Express.Express.Express a, Data.Express.Express.Express b, Data.Express.Express.Express c, Data.Express.Express.Express d, Data.Express.Express.Express e, Data.Express.Express.Express f) => Data.Express.Express.Express (a, b, c, d, e, f) instance (Data.Express.Express.Express a, Data.Express.Express.Express b, Data.Express.Express.Express c, Data.Express.Express.Express d, Data.Express.Express.Express e, Data.Express.Express.Express f, Data.Express.Express.Express g) => Data.Express.Express.Express (a, b, c, d, e, f, g) instance (Data.Express.Express.Express a, Data.Express.Express.Express b, Data.Express.Express.Express c, Data.Express.Express.Express d, Data.Express.Express.Express e, Data.Express.Express.Express f, Data.Express.Express.Express g, Data.Express.Express.Express h) => Data.Express.Express.Express (a, b, c, d, e, f, g, h) instance (Data.Express.Express.Express a, Data.Express.Express.Express b, Data.Express.Express.Express c, Data.Express.Express.Express d, Data.Express.Express.Express e, Data.Express.Express.Express f, Data.Express.Express.Express g, Data.Express.Express.Express h, Data.Express.Express.Express i) => Data.Express.Express.Express (a, b, c, d, e, f, g, h, i) instance (Data.Express.Express.Express a, Data.Express.Express.Express b, Data.Express.Express.Express c, Data.Express.Express.Express d, Data.Express.Express.Express e, Data.Express.Express.Express f, Data.Express.Express.Express g, Data.Express.Express.Express h, Data.Express.Express.Express i, Data.Express.Express.Express j) => Data.Express.Express.Express (a, b, c, d, e, f, g, h, i, j) instance (Data.Express.Express.Express a, Data.Express.Express.Express b, Data.Express.Express.Express c, Data.Express.Express.Express d, Data.Express.Express.Express e, Data.Express.Express.Express f, Data.Express.Express.Express g, Data.Express.Express.Express h, Data.Express.Express.Express i, Data.Express.Express.Express j, Data.Express.Express.Express k) => Data.Express.Express.Express (a, b, c, d, e, f, g, h, i, j, k) instance (Data.Express.Express.Express a, Data.Express.Express.Express b, Data.Express.Express.Express c, Data.Express.Express.Express d, Data.Express.Express.Express e, Data.Express.Express.Express f, Data.Express.Express.Express g, Data.Express.Express.Express h, Data.Express.Express.Express i, Data.Express.Express.Express j, Data.Express.Express.Express k, Data.Express.Express.Express l) => Data.Express.Express.Express (a, b, c, d, e, f, g, h, i, j, k, l) -- | Allows automatic derivation of Express typeclass instances. module Data.Express.Express.Derive -- | Derives an Express instance for the given type Name. -- -- This function needs the TemplateHaskell extension. -- -- If -:, ->:, ->>:, ->>>:, -- ... are not in scope, this will derive them as well. deriveExpress :: Name -> DecsQ -- | Derives a Express instance for a given type Name -- cascading derivation of type arguments as well. deriveExpressCascading :: Name -> DecsQ -- | Same as deriveExpress but does not warn when instance already -- exists (deriveExpress is preferable). deriveExpressIfNeeded :: Name -> DecsQ -- | Defines the Expr type and _basic_ utilities involving it, -- including: -- --

re-export of Data.Express.Core
re-export of Data.Express.Map
re-export of Data.Express.Fold
re-export of Data.Express.Hole

-- -- If you're a Express user, you're probably better of importing -- Data.Express. module Data.Express.Basic -- | Utilities for matching Exprs with variables. module Data.Express.Match -- | Given two expressions, returns a Just list of matches of -- subexpressions of the first expressions to variables in the second -- expression. Returns Nothing when there is no match. -- --

--   > let zero = val (0::Int)
--   > let one  = val (1::Int)
--   > let xx   = var "x" (undefined :: Int)
--   > let yy   = var "y" (undefined :: Int)
--   > let e1 -+- e2  =  value "+" ((+)::Int->Int->Int) :$ e1 :$ e2
--

-- --

--   > (zero -+- one) `match` (xx -+- yy)
--   Just [(y :: Int,1 :: Int),(x :: Int,0 :: Int)]
--

-- --

--   > (zero -+- (one -+- two)) `match` (xx -+- yy)
--   Just [(y :: Int,1 + 2 :: Int),(x :: Int,0 :: Int)]
--

-- --

--   > (zero -+- (one -+- two)) `match` (xx -+- (yy -+- yy))
--   Nothing
--

-- -- In short: -- --

--             (zero -+- one) `match` (xx -+- yy)           =  Just [(xx,zero), (yy,one)]
--   (zero -+- (one -+- two)) `match` (xx -+- yy)           =  Just [(xx,zero), (yy,one-+-two)]
--   (zero -+- (one -+- two)) `match` (xx -+- (yy -+- yy))  =  Nothing
--

match :: Expr -> Expr -> Maybe [(Expr, Expr)] -- | Like match but allowing predefined bindings. -- --

--   matchWith [(xx,zero)] (zero -+- one) (xx -+- yy)  =  Just [(xx,zero), (yy,one)]
--   matchWith [(xx,one)]  (zero -+- one) (xx -+- yy)  =  Nothing
--

matchWith :: [(Expr, Expr)] -> Expr -> Expr -> Maybe [(Expr, Expr)] -- | Given two Exprs, checks if the first expression is an instance -- of the second in terms of variables. (cf. hasInstanceOf) -- --

--   > let zero = val (0::Int)
--   > let one  = val (1::Int)
--   > let xx   = var "x" (undefined :: Int)
--   > let yy   = var "y" (undefined :: Int)
--   > let e1 -+- e2  =  value "+" ((+)::Int->Int->Int) :$ e1 :$ e2
--

-- --

--    one `isInstanceOf` one   =  True
--     xx `isInstanceOf` xx    =  True
--     yy `isInstanceOf` xx    =  True
--   zero `isInstanceOf` xx    =  True
--     xx `isInstanceOf` zero  =  False
--    one `isInstanceOf` zero  =  False
--     (xx -+- (yy -+- xx)) `isInstanceOf`   (xx -+- yy)  =  True
--     (yy -+- (yy -+- xx)) `isInstanceOf`   (xx -+- yy)  =  True
--   (zero -+- (yy -+- xx)) `isInstanceOf` (zero -+- yy)  =  True
--    (one -+- (yy -+- xx)) `isInstanceOf` (zero -+- yy)  =  False
--

isInstanceOf :: Expr -> Expr -> Bool -- | Checks if any of the subexpressions of the first argument Expr -- is an instance of the second argument Expr. hasInstanceOf :: Expr -> Expr -> Bool -- | O(n^2). Checks if an Expr is a subexpression of another. -- --

--   > (xx -+- yy) `isSubexprOf` (zz -+- (xx -+- yy))
--   True
--

-- --

--   > (xx -+- yy) `isSubexprOf` abs' (yy -+- xx)
--   False
--

-- --

--   > xx `isSubexprOf` yy
--   False
--

isSubexprOf :: Expr -> Expr -> Bool -- | Defines utilities do deal with instances of typeclasses -- -- Functions provided by this module store the set of instances as a -- simple Haskell list. When storing only a few instances this should be -- fine in terms of performance. -- -- If you plan to store hundreds or thousands of instances, we recommend -- implementing different versions that use a more efficient Set/Map -- storage. module Data.Express.Instances -- | O(1). Reifies an Eq instance into a list of -- Exprs. The list will contain == and /= for the -- given type. (cf. mkEq, mkEquation) -- --

--   > reifyEq (undefined :: Int)
--   [ (==) :: Int -> Int -> Bool
--   , (/=) :: Int -> Int -> Bool ]
--

-- --

--   > reifyEq (undefined :: Bool)
--   [ (==) :: Bool -> Bool -> Bool
--   , (/=) :: Bool -> Bool -> Bool ]
--

-- --

--   > reifyEq (undefined :: String)
--   [ (==) :: [Char] -> [Char] -> Bool
--   , (/=) :: [Char] -> [Char] -> Bool ]
--

reifyEq :: (Typeable a, Eq a) => a -> [Expr] -- | O(1). Reifies an Ord instance into a list of -- Exprs. The list will contain compare, <= and -- < for the given type. (cf. mkOrd, -- mkOrdLessEqual, mkComparisonLE, mkComparisonLT) -- --

--   > reifyOrd (undefined :: Int)
--   [ (<=) :: Int -> Int -> Bool
--   , (<) :: Int -> Int -> Bool ]
--

-- --

--   > reifyOrd (undefined :: Bool)
--   [ (<=) :: Bool -> Bool -> Bool
--   , (<) :: Bool -> Bool -> Bool ]
--

-- --

--   > reifyOrd (undefined :: [Bool])
--   [ (<=) :: [Bool] -> [Bool] -> Bool
--   , (<) :: [Bool] -> [Bool] -> Bool ]
--

reifyOrd :: (Typeable a, Ord a) => a -> [Expr] -- | O(1). Reifies Eq and Ord instances into a list of -- Expr. reifyEqOrd :: (Typeable a, Ord a) => a -> [Expr] -- | O(1). Reifies a Name instance into a list of -- Exprs. The list will contain name for the given type. -- (cf. mkName, lookupName, lookupNames) -- --

--   > reifyName (undefined :: Int)
--   [name :: Int -> [Char]]
--

-- --

--   > reifyName (undefined :: Bool)
--   [name :: Bool -> [Char]]
--

reifyName :: (Typeable a, Name a) => a -> [Expr] -- | O(1). Builds a reified Eq instance from the given -- == function. (cf. reifyEq) -- --

--   > mkEq ((==) :: Int -> Int -> Bool)
--   [ (==) :: Int -> Int -> Bool
--   , (/=) :: Int -> Int -> Bool ]
--

mkEq :: Typeable a => (a -> a -> Bool) -> [Expr] -- | O(1). Builds a reified Ord instance from the given -- compare function. (cf. reifyOrd, mkOrdLessEqual) mkOrd :: Typeable a => (a -> a -> Ordering) -> [Expr] -- | O(1). Builds a reified Ord instance from the given -- <= function. (cf. reifyOrd, mkOrd) mkOrdLessEqual :: Typeable a => (a -> a -> Bool) -> [Expr] -- | O(1). Builds a reified Name instance from the given -- name function. (cf. reifyName, mkNameWith) mkName :: Typeable a => (a -> String) -> [Expr] -- | O(1). Builds a reified Name instance from the given -- String and type. (cf. reifyName, mkName) mkNameWith :: Typeable a => String -> a -> [Expr] -- | O(n+m). Returns whether an Eq instance exists in the -- given instances list for the given Expr. -- --

--   > isEq (reifyEqOrd (undefined :: Int)) (val (0::Int))
--   True
--

-- --

--   > isEq (reifyEqOrd (undefined :: Int)) (val ([[[0::Int]]]))
--   False
--

-- -- Given that the instances list has length m and that the given -- Expr has size n, this function is O(n+m). isEq :: [Expr] -> Expr -> Bool -- | O(n+m). Returns whether an Ord instance exists in the -- given instances list for the given Expr. -- --

--   > isOrd (reifyEqOrd (undefined :: Int)) (val (0::Int))
--   True
--

-- --

--   > isOrd (reifyEqOrd (undefined :: Int)) (val ([[[0::Int]]]))
--   False
--

-- -- Given that the instances list has length m and that the given -- Expr has size n, this function is O(n+m). isOrd :: [Expr] -> Expr -> Bool -- | O(n+m). Returns whether both Eq and Ord instance -- exist in the given list for the given Expr. -- -- Given that the instances list has length m and that the given -- Expr has size n, this function is O(n+m). isEqOrd :: [Expr] -> Expr -> Bool -- | O(n). Returns whether an Eq instance exists in the given -- instances list for the given TypeRep. -- --

--   > isEqT (reifyEqOrd (undefined :: Int)) (typeOf (undefined :: Int))
--   True
--

-- --

--   > isEqT (reifyEqOrd (undefined :: Int)) (typeOf (undefined :: [[[Int]]]))
--   False
--

-- -- Given that the instances list has length n, this function is -- O(n). isEqT :: [Expr] -> TypeRep -> Bool -- | O(n). Returns whether an Ord instance exists in the -- given instances list for the given TypeRep. -- --

--   > isOrdT (reifyEqOrd (undefined :: Int)) (typeOf (undefined :: Int))
--   True
--

-- --

--   > isOrdT (reifyEqOrd (undefined :: Int)) (typeOf (undefined :: [[[Int]]]))
--   False
--

-- -- Given that the instances list has length n, this function is -- O(n). isOrdT :: [Expr] -> TypeRep -> Bool -- | O(n). Returns whether both Eq and Ord instance -- exist in the given list for the given TypeRep. -- -- Given that the instances list has length n, this function is -- O(n). isEqOrdT :: [Expr] -> TypeRep -> Bool mkEquation :: [Expr] -> Expr -> Expr -> Expr mkComparisonLE :: [Expr] -> Expr -> Expr -> Expr mkComparisonLT :: [Expr] -> Expr -> Expr -> Expr mkComparison :: String -> [Expr] -> Expr -> Expr -> Expr lookupComparison :: String -> TypeRep -> [Expr] -> Maybe Expr listVarsWith :: [Expr] -> Expr -> [Expr] lookupName :: [Expr] -> Expr -> String lookupNames :: [Expr] -> Expr -> [String] validApps :: [Expr] -> Expr -> [Expr] findValidApp :: [Expr] -> Expr -> Maybe Expr preludeNameInstances :: [Expr] -- | Utilities for canonicalizing Exprs with variables. module Data.Express.Canon -- | Canonicalizes an Expr so that variable names appear in order. -- Variable names are taken from the preludeNameInstances. -- --

--   > canonicalize (xx -+- yy)
--   x + y :: Int
--

-- --

--   > canonicalize (yy -+- xx)
--   x + y :: Int
--

-- --

--   > canonicalize (xx -+- xx)
--   x + x :: Int
--

-- --

--   > canonicalize (yy -+- yy)
--   x + x :: Int
--

-- -- Constants are untouched: -- --

--   > canonicalize (jj -+- (zero -+- abs' ii))
--   x + (y + abs y) :: Int
--

-- -- This also works for variable functions: -- --

--   > canonicalize (gg yy -+- ff xx -+- gg xx)
--   (f x + g y) + f y :: Int
--

canonicalize :: Expr -> Expr -- | Like canonicalize but allows customization of the list of -- variable names. (cf. lookupNames, -- variableNamesFromTemplate) -- --

--   > canonicalizeWith (const ["i","j","k","l",...]) (xx -+- yy)
--   i + j :: Int
--

-- -- The argument Expr of the argument function allows to provide a -- different list of names for different types: -- --

--   > let namesFor e
--   >   | typ e == typeOf (undefined::Char) = variableNamesFromTemplate "c1"
--   >   | typ e == typeOf (undefined::Int)  = variableNamesFromTemplate "i"
--   >   | otherwise                         = variableNamesFromTemplate "x"
--

-- --

--   > canonicalizeWith namesFor ((xx -+- ord' dd) -+- (ord' cc -+- yy))
--   (i + ord c1) + (ord c2 + j) :: Int
--

canonicalizeWith :: (Expr -> [String]) -> Expr -> Expr -- | Return a canonicalization of an Expr that makes variable names -- appear in order using names as provided by -- preludeNameInstances. By using //- it can -- canonicalize Exprs. -- --

--   > canonicalization (gg yy -+- ff xx -+- gg xx)
--   [ (x :: Int,        y :: Int)
--   , (f :: Int -> Int, g :: Int -> Int)
--   , (y :: Int,        x :: Int)
--   , (g :: Int -> Int, f :: Int -> Int) ]
--

-- --

--   > canonicalization (yy -+- xx -+- yy)
--   [ (x :: Int, y :: Int)
--   , (y :: Int, x :: Int) ]
--

canonicalization :: Expr -> [(Expr, Expr)] -- | Like canonicalization but allows customization of the list of -- variable names. (cf. lookupNames, -- variableNamesFromTemplate) canonicalizationWith :: (Expr -> [String]) -> Expr -> [(Expr, Expr)] -- | Returns whether an Expr is canonical: if applying -- canonicalize is an identity using names as provided by -- preludeNameInstances. isCanonical :: Expr -> Bool -- | Like isCanonical but allows specifying the list of variable -- names. isCanonicalWith :: (Expr -> [String]) -> Expr -> Bool -- | Returns all canonical variations of an Expr by filling holes -- with variables. Where possible, variations are listed from most -- general to least general. -- --

--   > canonicalVariations $ i_
--   [x :: Int]
--

-- --

--   > canonicalVariations $ i_ -+- i_
--   [ x + y :: Int
--   , x + x :: Int ]
--

-- --

--   > canonicalVariations $ i_ -+- i_ -+- i_
--   [ (x + y) + z :: Int
--   , (x + y) + x :: Int
--   , (x + y) + y :: Int
--   , (x + x) + y :: Int
--   , (x + x) + x :: Int ]
--

-- --

--   > canonicalVariations $ i_ -+- ord' c_
--   [x + ord c :: Int]
--

-- --

--   > canonicalVariations $ i_ -+- i_ -+- ord' c_
--   [ (x + y) + ord c :: Int
--   , (x + x) + ord c :: Int ]
--

-- --

--   > canonicalVariations $ i_ -+- i_ -+- length' (c_ -:- unit c_)
--   [ (x + y) + length (c:d:"") :: Int
--   , (x + y) + length (c:c:"") :: Int
--   , (x + x) + length (c:d:"") :: Int
--   , (x + x) + length (c:c:"") :: Int ]
--

-- -- In an expression without holes this functions just returns a singleton -- list with the expression itself: -- --

--   > canonicalVariations $ val (0 :: Int)
--   [0 :: Int]
--

-- --

--   > canonicalVariations $ ord' bee
--   [ord 'b' :: Int]
--

-- --

--   > canonicalVariations $ ii -+- jj
--   [i + j :: Int]
--

-- -- Behaviour is undefined when applying this function to expressions -- already containing variables. canonicalVariations :: Expr -> [Expr] -- | A faster version of canonicalVariations that disregards name -- clashes across different types. Results are confusing to the user but -- fine for Express which differentiates between variables with the same -- name but different types. -- -- Without applying canonicalize, the following Expr may -- seem to have only one variable: -- --

--   > fastCanonicalVariations $ i_ -+- ord' c_
--   [x + ord x :: Int]
--

-- -- Where in fact it has two, as the second x has a different -- type. Applying canonicalize disambiguates: -- --

--   > map canonicalize . fastCanonicalVariations $ i_ -+- ord' c_
--   [x + ord c :: Int]
--

-- -- This function is useful when resulting Exprs are not intended -- to be presented to the user but instead to be used by another -- function. It is simply faster to skip the step where clashes are -- resolved. fastCanonicalVariations :: Expr -> [Expr] -- | Express is a library for manipulating dynamically typed Haskell -- expressions. It's like Data.Dynamic but with support for -- encoding applications and variables. -- -- It provides the Expr type and over a hundred functions for -- building, evaluating, comparing, folding, canonicalizing and matching -- Exprs. -- -- Basics. For types that are Show instances, we can use -- val to encode values as Exprs: -- --

--   > let false = val False
--   > :t false
--   false :: Expr
--   > print false
--   False :: Bool
--

-- -- As seen above, the Show instance for Expr produces a -- string with the encoded value and it's type. -- -- For types that aren't Show instances, like functions, we can -- use value to encode values as Exprs. -- --

--   > let notE = value "not" not
--   > :t notE
--   notE :: Expr
--   > print notE
--   not :: Bool -> Bool
--

-- -- Using :$ we can apply function valued Exprs, to other -- Exprs. -- --

--   > let notFalse = notE :$ false
--   > :t notFalse
--   notFalse :: Expr
--   > notFalse
--   not False :: Bool
--

-- -- Using evaluate or eval we can evaluate Exprs back -- into a regular Haskell value. -- --

--   > evaluate notFalse :: Maybe Bool
--   Just True
--   > evaluate notFalse :: Maybe Int
--   Nothing
--   > eval False notFalse
--   True
--   > eval (0::Int) notFalse
--   0
--

-- -- Example: Like with Data.Dynamic, we can use Express to -- create heterogeneous lists: -- --

--   > let xs = [val False, val True, val (1::Int), val (2::Int), val (3::Integer), val "123"]
--   > :t xs
--   xs :: [Expr]
--   > xs
--   [ False :: Bool
--   , True :: Bool
--   , 1 :: Int
--   , 2 :: Int
--   , 3 :: Integer
--   , "123" :: [Char]
--   ]
--

-- -- We can then apply evaluate to select values of different types: -- --

--   > import Data.Maybe
--   > mapMaybe evaluate xs :: [Bool]
--   [False,True]
--   > mapMaybe evaluate xs :: [Int]
--   [1,2]
--   > mapMaybe evaluate xs :: [Integer]
--   [3]
--   > mapMaybe evaluate xs :: [String]
--   ["123"]
--

-- -- If we define an heterogeneous list of functions encoded as -- Exprs: -- --

--   > let fs = [value "not" not, value "&&" (&&), value "abs" (abs :: Int -> Int)]
--   > :t fs
--   fs :: [Expr]
--

-- -- Using $$ we can list the type correct applications between the -- two previously defined lists: -- --

--   > catMaybes [f $$ x | f <- fs, x <- xs]
--   [ not False :: Bool
--   , not True :: Bool
--   , (False &&) :: Bool -> Bool
--   , (True &&) :: Bool -> Bool
--   , abs 1 :: Int
--   , abs 2 :: Int
--   ]
--

-- -- Other uses of Express include: -- --

generalizing counter-examples of property-based testing in -- Extrapolate;
conjecturing equations based on the results of testing in -- Speculate.

-- -- In this documentation, the complexity of most functions is given in -- big O notation where n is the size of the expression being -- manipulated or produced. There may still be a m cost associated -- with the values being stored in Exprs. module Data.Express -- | Values of type Expr represent objects or applications between -- objects. Each object is encapsulated together with its type and string -- representation. Values encoded in Exprs are always monomorphic. -- -- An Expr can be constructed using: -- --

val, for values that are Show instances;
value, for values that are not Show instances, like -- functions;
:$, for applications between Exprs.

-- --

--   > val False
--   False :: Bool
--

-- --

--   > value "not" not :$ val False
--   not False :: Bool
--

-- -- An Expr can be evaluated using evaluate, eval or -- evl. -- --

--   > evl $ val (1 :: Int) :: Int
--   1
--

-- --

--   > evaluate $ val (1 :: Int) :: Maybe Bool
--   Nothing
--

-- --

--   > eval 'a' (val 'b')
--   'b'
--

-- -- Showing a value of type Expr will return a -- pretty-printed representation of the expression together with its -- type. -- --

--   > show (value "not" not :$ val False)
--   "not False :: Bool"
--

--   > value "0" (0 :: Integer)
--   0 :: Integer
--

-- --

--   > value "'a'" 'a'
--   'a' :: Char
--

-- --

--   > value "True" True
--   True :: Bool
--

-- --

--   > value "id" (id :: Int -> Int)
--   id :: Int -> Int
--

-- --

--   > value "(+)" ((+) :: Int -> Int -> Int)
--   (+) :: Int -> Int -> Int
--

-- --

--   > value "sort" (sort :: [Bool] -> [Bool])
--   sort :: [Bool] -> [Bool]
--

value :: Typeable a => String -> a -> Expr -- | O(1). A shorthand for value for values that are -- Show instances. -- --

--   > val (0 :: Int)
--   0 :: Int
--

-- --

--   > val 'a'
--   'a' :: Char
--

-- --

--   > val True
--   True :: Bool
--

-- -- Example equivalences to value: -- --

--   val 0     =  value "0" 0
--   val 'a'   =  value "'a'" 'a'
--   val True  =  value "True" True
--

val :: (Typeable a, Show a) => a -> Expr -- | O(n). Creates an Expr representing a function -- application. Just an Expr application if the types -- match, Nothing otherwise. (cf. :$) -- --

--   > value "id" (id :: () -> ()) $$ val ()
--   Just (id () :: ())
--

-- --

--   > value "abs" (abs :: Int -> Int) $$ val (1337 :: Int)
--   Just (abs 1337 :: Int)
--

-- --

--   > value "abs" (abs :: Int -> Int) $$ val 'a'
--   Nothing
--

-- --

--   > value "abs" (abs :: Int -> Int) $$ val ()
--   Nothing
--

($$) :: Expr -> Expr -> Maybe Expr -- | O(1). Creates an Expr representing a variable with the -- given name and argument type. -- --

--   > var "x" (undefined :: Int)
--   x :: Int
--

-- --

--   > var "u" (undefined :: ())
--   u :: ()
--

-- --

--   > var "xs" (undefined :: [Int])
--   xs :: [Int]
--

--   > let one = val (1 :: Int)
--   > let bee = val 'b'
--   > let negateE = value "negate" (negate :: Int -> Int)
--

-- --

--   > evaluate one :: Maybe Int
--   Just 1
--

-- --

--   > evaluate one :: Maybe Char
--   Nothing
--

-- --

--   > evaluate bee :: Maybe Int
--   Nothing
--

-- --

--   > evaluate bee :: Maybe Char
--   Just 'b'
--

-- --

--   > evaluate $ negateE :$ one :: Maybe Int
--   Just (-1)
--

-- --

--   > evaluate $ negateE :$ bee :: Maybe Int
--   Nothing
--

evaluate :: Typeable a => Expr -> Maybe a -- | O(n). Evaluates an expression when possible (correct type). -- Returns a default value otherwise. -- --

--   > let two = val (2 :: Int)
--   > let three = val (3 :: Int)
--   > let e1 -+- e2 = value "+" ((+) :: Int->Int->Int) :$ e1 :$ e2
--

-- --

--   > eval 0 $ two -+- three :: Int
--   5
--

-- --

--   > eval 'z' $ two -+- three :: Char
--   'z'
--

-- --

--   > eval 0 $ two -+- val '3' :: Int
--   0
--

eval :: Typeable a => a -> Expr -> a -- | O(n). Evaluates an expression when possible (correct type). -- Raises an error otherwise. -- --

--   > evl $ two -+- three :: Int
--   5
--

-- --

--   > evl $ two -+- three :: Bool
--   *** Exception: evl: cannot evaluate Expr `2 + 3 :: Int' at the Bool type
--

--   > let one = val (1 :: Int)
--   > let bee = val 'b'
--   > let absE = value "abs" (abs :: Int -> Int)
--

-- --

--   > typ one
--   Int
--

-- --

--   > typ bee
--   Char
--

-- --

--   > typ absE
--   Int -> Int
--

-- --

--   > typ (absE :$ one)
--   Int
--

-- --

--   > typ (absE :$ bee)
--   *** Exception: type mismatch, cannot apply `Int -> Int' to `Char'
--

-- --

--   > typ ((absE :$ bee) :$ one)
--   *** Exception: type mismatch, cannot apply `Int -> Int' to `Char'
--

--   > let one = val (1 :: Int)
--   > let bee = val 'b'
--   > let absE = value "abs" (abs :: Int -> Int)
--

-- --

--   > etyp one
--   Right Int
--

-- --

--   > etyp bee
--   Right Char
--

-- --

--   > etyp absE
--   Right (Int -> Int)
--

-- --

--   > etyp (absE :$ one)
--   Right Int
--

-- --

--   > etyp (absE :$ bee)
--   Left (Int -> Int, Char)
--

-- --

--   > etyp ((absE :$ bee) :$ one)
--   Left (Int -> Int, Char)
--

etyp :: Expr -> Either (TypeRep, TypeRep) TypeRep -- | O(n). Returns Just the type of an expression or -- Nothing when there is an error. -- --

--   > let one = val (1 :: Int)
--   > let bee = val 'b'
--   > let absE = value "abs" (abs :: Int -> Int)
--

-- --

--   > mtyp one
--   Just Int
--

-- --

--   > mtyp (absE :$ bee)
--   Nothing
--

mtyp :: Expr -> Maybe TypeRep -- | O(n). Evaluates an expression to a terminal Dynamic -- value when possible. Returns Nothing otherwise. -- --

--   > toDynamic $ val (123 :: Int) :: Maybe Dynamic
--   Just <<Int>>
--

-- --

--   > toDynamic $ value "abs" (abs :: Int -> Int) :$ val (-1 :: Int)
--   Just <<Int>>
--

-- --

--   > toDynamic $ value "abs" (abs :: Int -> Int) :$ val 'a'
--   Nothing
--

toDynamic :: Expr -> Maybe Dynamic -- | O(1). Returns whether an Expr is a terminal value -- (Value). -- --

--   > isValue $ var "x" (undefined :: Int)
--   True
--

-- --

--   > isValue $ val False
--   True
--

-- --

--   > isValue $ value "not" not :$ var "p" (undefined :: Bool)
--   False
--

-- -- This is equivalent to pattern matching the Value constructor. -- -- Properties: -- --

```
 isValue (Value e) = True
```
```
 isValue (e1 :$ e2) = False
```
```
 isValue = not . isApp
```
```
 isValue e = isVar e || isConst e
```

isValue :: Expr -> Bool -- | O(1). Returns whether an Expr is an application -- (:$). -- --

--   > isApp $ var "x" (undefined :: Int)
--   False
--

-- --

--   > isApp $ val False
--   False
--

-- --

--   > isApp $ value "not" not :$ var "p" (undefined :: Bool)
--   True 
--

-- -- This is equivalent to pattern matching the :$ constructor. -- -- Properties: -- --

```
 isApp (e1 :$ e2) = True
```
```
 isApp (Value e) = False
```
```
 isApp = not . isValue
```

 isApp e = not (isVar e) && not (isConst
--   e)

isApp :: Expr -> Bool -- | O(1). Returns whether an Expr is a terminal variable -- (var). (cf. hasVar). -- --

--   > isVar $ var "x" (undefined :: Int)
--   True
--

-- --

--   > isVar $ val False
--   False
--

-- --

--   > isVar $ value "not" not :$ var "p" (undefined :: Bool)
--   False
--

isVar :: Expr -> Bool -- | O(1). Returns whether an Expr is a terminal constant. -- (cf. isGround). -- --

--   > isConst $ var "x" (undefined :: Int)
--   False
--

-- --

--   > isConst $ val False
--   True
--

-- --

--   > isConst $ value "not" not :$ val False
--   False
--

isConst :: Expr -> Bool -- | O(n). Returns whether the given Expr is ill typed. (cf. -- isWellTyped) -- --

--   > let one = val (1 :: Int)
--   > let bee = val 'b'
--   > let absE = value "abs" (abs :: Int -> Int)
--

-- --

--   > isIllTyped (absE :$ val (1 :: Int))
--   False
--

-- --

--   > isIllTyped (absE :$ val 'b')
--   True
--

isIllTyped :: Expr -> Bool -- | O(n). Returns whether the given Expr is well typed. (cf. -- isIllTyped) -- --

--   > isWellTyped (absE :$ val (1 :: Int))
--   True
--

-- --

--   > isWellTyped (absE :$ val 'b')
--   False
--

isWellTyped :: Expr -> Bool -- | O(n). Check if an Expr has a variable. (By convention, -- any value whose String representation starts with -- '_'.) -- --

--   > hasVar $ value "not" not :$ val True
--   False
--

-- --

--   > hasVar $ value "&&" (&&) :$ var "p" (undefined :: Bool) :$ val True
--   True
--

hasVar :: Expr -> Bool -- | O(n). Returns whether a Expr has no variables. -- This is equivalent to "not . hasVar". -- -- The name "ground" comes from term rewriting. -- --

--   > isGround $ value "not" not :$ val True
--   True
--

-- --

--   > isGround $ value "&&" (&&) :$ var "p" (undefined :: Bool) :$ val True
--   False
--

e1 is smaller in size/length than e2, e.g.: x + -- y < x + (y + z);
or, e1 has more distinct variables than e2, e.g.: -- x + y < x + x;
or, e1 has more variable occurrences than e2, e.g.: -- x + x < 1 + x;
or, e1 has fewer distinct constants than e2, e.g.: -- 1 + 1 < 0 + 1.

-- -- They're otherwise considered of equal complexity, e.g.: x + y -- and y + z. -- --

--   > (xx -+- yy) `compareComplexity` (xx -+- (yy -+- zz))
--   LT
--

-- --

--   > (xx -+- yy) `compareComplexity` (xx -+- xx)
--   LT
--

-- --

--   > (xx -+- xx) `compareComplexity` (one -+- xx)
--   LT
--

-- --

--   > (one -+- one) `compareComplexity` (zero -+- one)
--   LT
--

-- --

--   > (xx -+- yy) `compareComplexity` (yy -+- zz)
--   EQ
--

-- --

--   > (zero -+- one) `compareComplexity` (one -+- zero)
--   EQ
--

compareComplexity :: Expr -> Expr -> Ordering -- | O(n). Return the arity of the given expression, i.e. the number -- of arguments that its type takes. -- --

--   > arity (val (0::Int))
--   0
--

-- --

--   > arity (val False)
--   0
--

-- --

--   > arity (value "id" (id :: Int -> Int))
--   1
--

-- --

--   > arity (value "const" (const :: Int -> Int -> Int))
--   2
--

-- --

--   > arity (one -+- two)
--   0
--

arity :: Expr -> Int -- | O(n). Returns the size of the given expression, i.e. the number -- of terminal values in it. -- --

--   zero       =  val (0 :: Int)
--   one        =  val (1 :: Int)
--   two        =  val (2 :: Int)
--   xx -+- yy  =  value "+" ((+) :: Int->Int->Int) :$ xx :$ yy
--   abs' xx    =  value "abs" (abs :: Int->Int) :$ xx
--

-- --

--   > size zero
--   1
--

-- --

--   > size (one -+- two)
--   3
--

-- --

--   > size (abs' one)
--   2
--

--   zero       =  val (0 :: Int)
--   one        =  val (1 :: Int)
--   two        =  val (2 :: Int)
--   xx -+- yy  =  value "+" ((+) :: Int->Int->Int) :$ xx :$ yy
--   abs' xx    =  value "abs" (abs :: Int->Int) :$ xx
--

-- --

--   > depth zero
--   1
--

-- --

--   > depth (one -+- two)
--   2
--

-- --

--   > depth (abs' one -+- two)
--   3
--

--   zero          =  val (0 :: Int)
--   one           =  val (1 :: Int)
--   two           =  val (2 :: Int)
--   const' xx yy  =  value "const" (const :: Int->Int->Int) :$ xx :$ yy
--   abs' xx       =  value "abs" (abs :: Int->Int) :$ xx
--

-- -- Then: -- --

--   > height zero
--   1
--

-- --

--   > height (abs' one)
--   2
--

-- --

--   > height ((const' one) two)
--   3
--

-- --

--   > height ((const' (abs' one)) two)
--   4
--

-- --

--   > height ((const' one) (abs' two))
--   3
--

-- -- Flipping arguments of applications in subterms may change the result -- of the function. height :: Expr -> Int -- | O(n). Returns a string representation of an expression. -- Differently from show (:: Expr -> String) this -- function does not include the type in the output. -- --

--   > putStrLn $ showExpr (one -+- two)
--   1 + 2
--

-- --

--   > putStrLn $ showExpr $ (pp -||- true) -&&- (qq -||- false)
--   (p || True) && (q || False)
--

showExpr :: Expr -> String showPrecExpr :: Int -> Expr -> String showOpExpr :: String -> Expr -> String -- | O(n) for the spine, O(n^2) for full evaluation. Lists -- subexpressions of a given expression in order and with repetitions. -- This includes the expression itself and partial function applications. -- (cf. nubSubexprs) -- --

--   > subexprs (xx -+- yy)
--   [ x + y :: Int
--   , (x +) :: Int -> Int
--   , (+) :: Int -> Int -> Int
--   , x :: Int
--   , y :: Int
--   ]
--

-- --

--   > subexprs (pp -&&- (pp -&&- true))
--   [ p && (p && True) :: Bool
--   , (p &&) :: Bool -> Bool
--   , (&&) :: Bool -> Bool -> Bool
--   , p :: Bool
--   , p && True :: Bool
--   , (p &&) :: Bool -> Bool
--   , (&&) :: Bool -> Bool -> Bool
--   , p :: Bool
--   , True :: Bool
--   ]
--

subexprs :: Expr -> [Expr] -- | O(n). Lists all terminal values in an expression in order and -- with repetitions. (cf. nubValues) -- --

--   > values (xx -+- yy)
--   [ (+) :: Int -> Int -> Int
--   , x :: Int
--   , y :: Int
--   ]
--

-- --

--   > values (xx -+- (yy -+- zz))
--   [ (+) :: Int -> Int -> Int
--   , x :: Int
--   , (+) :: Int -> Int -> Int
--   , y :: Int
--   , z :: Int
--   ]
--

-- --

--   > values (zero -+- (one -*- two))
--   [ (+) :: Int -> Int -> Int
--   , 0 :: Int
--   , (*) :: Int -> Int -> Int
--   , 1 :: Int
--   , 2 :: Int
--   ]
--

-- --

--   > values (pp -&&- true)
--   [ (&&) :: Bool -> Bool -> Bool
--   , p :: Bool
--   , True :: Bool
--   ]
--

values :: Expr -> [Expr] -- | O(n). Lists all variables in an expression in order and with -- repetitions. (cf. nubVars) -- --

--   > vars (xx -+- yy)
--   [ x :: Int
--   , y :: Int
--   ]
--

-- --

--   > vars (xx -+- (yy -+- xx))
--   [ x :: Int
--   , y :: Int
--   , x :: Int
--   ]
--

-- --

--   > vars (zero -+- (one -*- two))
--   []
--

-- --

--   > vars (pp -&&- true)
--   [p :: Bool]
--

vars :: Expr -> [Expr] -- | O(n). List terminal constants in an expression in order and -- with repetitions. (cf. nubConsts) -- --

--   > consts (xx -+- yy)
--   [ (+) :: Int -> Int -> Int ]
--

-- --

--   > consts (xx -+- (yy -+- zz))
--   [ (+) :: Int -> Int -> Int
--   , (+) :: Int -> Int -> Int
--   ]
--

-- --

--   > consts (zero -+- (one -*- two))
--   [ (+) :: Int -> Int -> Int
--   , 0 :: Int
--   , (*) :: Int -> Int -> Int
--   , 1 :: Int
--   , 2 :: Int
--   ]
--

-- --

--   > consts (pp -&&- true)
--   [ (&&) :: Bool -> Bool -> Bool
--   , True :: Bool
--   ]
--

--   > nubSubexprs (xx -+- yy)
--   [ x :: Int
--   , y :: Int
--   , (+) :: Int -> Int -> Int
--   , (x +) :: Int -> Int
--   , x + y :: Int
--   ]
--

-- --

--   > nubSubexprs (pp -&&- (pp -&&- true))
--   [ p :: Bool
--   , True :: Bool
--   , (&&) :: Bool -> Bool -> Bool
--   , (p &&) :: Bool -> Bool
--   , p && True :: Bool
--   , p && (p && True) :: Bool
--   ]
--

nubSubexprs :: Expr -> [Expr] -- | O(n log n). Lists all terminal values in an expression without -- repetitions. (cf. values) -- --

--   > nubValues (xx -+- yy)
--   [ x :: Int
--   , y :: Int
--   , (+) :: Int -> Int -> Int
--

-- -- ] -- --

--   > nubValues (xx -+- (yy -+- zz))
--   [ x :: Int
--   , y :: Int
--   , z :: Int
--   , (+) :: Int -> Int -> Int
--   ]
--

-- --

--   > nubValues (zero -+- (one -*- two))
--   [ 0 :: Int
--   , 1 :: Int
--   , 2 :: Int
--   , (*) :: Int -> Int -> Int
--   , (+) :: Int -> Int -> Int
--   ]
--

-- --

--   > nubValues (pp -&&- pp)
--   [ p :: Bool
--   , (&&) :: Bool -> Bool -> Bool
--   ]
--

nubValues :: Expr -> [Expr] -- | O(n log n). Lists all variables in an expression without -- repetitions. (cf. vars) -- --

--   > nubVars (yy -+- xx)
--   [ x :: Int
--   , y :: Int
--   ]
--

-- --

--   > nubVars (xx -+- (yy -+- xx))
--   [ x :: Int
--   , y :: Int
--   ]
--

-- --

--   > nubVars (zero -+- (one -*- two))
--   []
--

-- --

--   > nubVars (pp -&&- true)
--   [p :: Bool]
--

nubVars :: Expr -> [Expr] -- | O(n log n). List terminal constants in an expression without -- repetitions. (cf. consts) -- --

--   > nubConsts (xx -+- yy)
--   [ (+) :: Int -> Int -> Int ]
--

-- --

--   > nubConsts (xx -+- (yy -+- zz))
--   [ (+) :: Int -> Int -> Int ]
--

-- --

--   > nubConsts (pp -&&- true)
--   [ True :: Bool
--   , (&&) :: Bool -> Bool -> Bool
--   ]
--

nubConsts :: Expr -> [Expr] -- | O(n*m). Applies a function to all terminal values in an -- expression. (cf. //-) -- -- Given that: -- --

--   > let zero  = val (0 :: Int)
--   > let one   = val (1 :: Int)
--   > let two   = val (2 :: Int)
--   > let three = val (3 :: Int)
--   > let xx -+- yy = value "+" ((+) :: Int->Int->Int) :$ xx :$ yy
--   > let intToZero e = if typ e == typ zero then zero else e
--

-- -- Then: -- --

--   > one -+- (two -+- three)
--   1 + (2 + 3) :: Int
--

-- --

--   > mapValues intToZero $ one -+- (two -+- three)
--   0 + (0 + 0) :: Integer
--

--   > let primeify e = if isVar e
--   |                  then case e of (Value n d) -> Value (n ++ "'") d
--   |                  else e
--   > let xx = var "x" (undefined :: Int)
--   > let yy = var "y" (undefined :: Int)
--   > let xx -+- yy = value "+" ((+) :: Int->Int->Int) :$ xx :$ yy
--

-- -- Then: -- --

--   > xx -+- yy
--   x + y :: Int
--

-- --

--   > primeify xx
--   x' :: Int
--

-- --

--   > mapVars primeify $ xx -+- yy
--   x' + y' :: Int
--

-- --

--   > mapVars (primeify . primeify) $ xx -+- yy
--   x'' + y'' :: Int
--

--   > let one   = val (1 :: Int)
--   > let two   = val (2 :: Int)
--   > let xx -+- yy = value "+" ((+) :: Int->Int->Int) :$ xx :$ yy
--   > let intToZero e = if typ e == typ zero then zero else e
--

-- -- Then: -- --

--   > one -+- (two -+- xx)
--   1 + (2 + x) :: Int
--

-- --

--   > mapConsts intToZero (one -+- (two -+- xx))
--   0 + (0 + x) :: Integer
--

--   > let xx = var "x" (undefined :: Int)
--   > let yy = var "y" (undefined :: Int)
--   > let zz = var "z" (undefined :: Int)
--   > let plus = value "+" ((+) :: Int->Int->Int)
--   > let times = value "*" ((*) :: Int->Int->Int)
--   > let xx -+- yy = plus :$ xx :$ yy
--   > let xx -*- yy = times :$ xx :$ yy
--

-- --

--   > let pluswap (o :$ xx :$ yy) | o == plus = Just $ o :$ yy :$ xx
--   |     pluswap _                           = Nothing
--

-- -- Then: -- --

--   > mapSubexprs pluswap $ (xx -*- yy) -+- (yy -*- zz)
--   y * z + x * y :: Int
--

-- --

--   > mapSubexprs pluswap $ (xx -+- yy) -*- (yy -+- zz)
--   (y + x) * (z + y) :: Int
--

-- -- Substitutions do not stack, in other words a replaced expression or -- its subexpressions are not further replaced: -- --

--   > mapSubexprs pluswap $ (xx -+- yy) -+- (yy -+- zz)
--   (y + z) + (x + y) :: Int
--

--   > let xx = var "x" (undefined :: Int)
--   > let yy = var "y" (undefined :: Int)
--   > let zz = var "z" (undefined :: Int)
--   > let xx -+- yy = value "+" ((+) :: Int->Int->Int) :$ xx :$ yy
--

-- -- Then: -- --

--   > ((xx -+- yy) -+- (yy -+- zz)) //- [(xx, yy), (zz, yy)]
--   (y + y) + (y + y) :: Int
--

-- --

--   > ((xx -+- yy) -+- (yy -+- zz)) //- [(yy, yy -+- zz)]
--   (x + (y + z)) + ((y + z) + z) :: Int
--

-- -- This function does not work for substituting non-terminal -- subexpressions: -- --

--   > (xx -+- yy) //- [(xx -+- yy, zz)]
--   x + y :: Int
--

-- -- Please use the slower // if you want the above replacement to -- work. -- -- Replacement happens only once: -- --

--   > xx //- [(xx,yy), (yy,zz)]
--   y :: Int
--

--   > let xx = var "x" (undefined :: Int)
--   > let yy = var "y" (undefined :: Int)
--   > let zz = var "z" (undefined :: Int)
--   > let xx -+- yy = value "+" ((+) :: Int->Int->Int) :$ xx :$ yy
--

-- -- Then: -- --

--   > ((xx -+- yy) -+- (yy -+- zz)) // [(xx -+- yy, yy), (yy -+- zz, yy)]
--   y + y :: Int
--

-- --

--   > ((xx -+- yy) -+- zz) // [(xx -+- yy, zz), (zz, xx -+- yy)]
--   z + (x + y) :: Int
--

-- -- Replacement happens only once with outer expressions having more -- precedence than inner expressions. -- --

--   > (xx -+- yy) // [(yy,xx), (xx -+- yy,zz), (zz,xx)]
--   z :: Int
--

--   > renameVarsBy (++ "'") (xx -+- yy)
--   x' + y' :: Int
--

-- --

--   > renameVarsBy (++ "'") (yy -+- (zz -+- xx))
--   (y' + (z' + x')) :: Int
--

-- --

--   > renameVarsBy (++ "1") (abs' xx)
--   abs x1 :: Int
--

-- --

--   > renameVarsBy (++ "2") $ abs' (xx -+- yy)
--   abs (x2 + y2) :: Int
--

-- -- NOTE: this will affect holes! renameVarsBy :: (String -> String) -> Expr -> Expr -- | O(1). Creates a variable with the same type as the given -- Expr. -- --

--   > let one = val (1::Int)
--   > "x" `varAsTypeOf` one
--   x :: Int
--

-- --

--   > "p" `varAsTypeOf` val False
--   p :: Bool
--

varAsTypeOf :: String -> Expr -> Expr -- | Generate an infinite list of variables based on a template and a given -- type. (cf. listVarsAsTypeOf) -- --

--   > putL 10 $ listVars "x" (undefined :: Int)
--   [ x :: Int
--   , y :: Int
--   , z :: Int
--   , x' :: Int
--   , y' :: Int
--   , z' :: Int
--   , x'' :: Int
--   , ...
--   ]
--

-- --

--   > putL 10 $ listVars "p" (undefined :: Bool)
--   [ p :: Bool
--   , q :: Bool
--   , r :: Bool
--   , p' :: Bool
--   , q' :: Bool
--   , r' :: Bool
--   , p'' :: Bool
--   , ...
--   ]
--

listVars :: Typeable a => String -> a -> [Expr] -- | Generate an infinite list of variables based on a template and the -- type of a given Expr. (cf. listVars) -- --

--   > let one = val (1::Int)
--   > putL 10 $ "x" `listVarsAsTypeOf` one
--   [ x :: Int
--   , y :: Int
--   , z :: Int
--   , x' :: Int
--   , ...
--   ]
--

-- --

--   > let false = val False
--   > putL 10 $ "p" `listVarsAsTypeOf` false
--   [ p :: Bool
--   , q :: Bool
--   , r :: Bool
--   , p' :: Bool
--   , ...
--   ]
--

listVarsAsTypeOf :: String -> Expr -> [Expr] -- | O(1). Creates an Expr representing a typed hole of the -- given argument type. -- --

--   > hole (undefined :: Int)
--   _ :: Int
--

-- --

--   > hole (undefined :: Maybe String)
--   _ :: Maybe [Char]
--

-- -- A hole is represented as a variable with no name or a value named -- "_": -- --

--   hole x = var "" x
--   hole x = value "_" x
--

hole :: Typeable a => a -> Expr -- | O(1). Checks if an Expr represents a typed hole. (cf. -- hole) -- --

--   > isHole $ hole (undefined :: Int)
--   True
--

-- --

--   > isHole $ value "not" not :$ val True
--   False
--

-- --

--   > isHole $ val 'a'
--   False
--

isHole :: Expr -> Bool -- | O(n). Lists all holes in an expression, in order and with -- repetitions. (cf. nubHoles) -- --

--   > holes $ hole (undefined :: Bool)
--   [_ :: Bool]
--

-- --

--   > holes $ value "&&" (&&) :$ hole (undefined :: Bool) :$ hole (undefined :: Bool)
--   [_ :: Bool,_ :: Bool]
--

-- --

--   > holes $ hole (undefined :: Bool->Bool) :$ hole (undefined::Bool)
--   [_ :: Bool -> Bool,_ :: Bool]
--

holes :: Expr -> [Expr] -- | O(n log n). Lists all holes in an expression without -- repetitions. (cf. holes) -- --

--   > nubHoles $ hole (undefined :: Bool)
--   [_ :: Bool]
--

-- --

--   > nubHoles $ value "&&" (&&) :$ hole (undefined :: Bool) :$ hole (undefined :: Bool)
--   [_ :: Bool]
--

-- --

--   > nubHoles $ hole (undefined :: Bool->Bool) :$ hole (undefined::Bool)
--   [_ :: Bool,_ :: Bool -> Bool]
--

nubHoles :: Expr -> [Expr] -- | O(1). Creates an Expr representing a typed hole with the -- type of the given Expr. (cf. hole) -- --

--   > val (1::Int)
--   1 :: Int
--   > holeAsTypeOf $ val (1::Int)
--   _ :: Int
--

holeAsTypeOf :: Expr -> Expr -- | O(n). Folds a list of Exprs into a single Expr. -- (cf. unfold) -- -- This always generates an ill-typed expression. -- --

--   fold [val False, val True, val (1::Int)]
--   [False,True,1] :: ill-typed # ExprList $ Bool #
--

-- -- This is useful when applying transformations on lists of Exprs, -- such as canonicalize, mapValues or -- canonicalVariations. -- --

--   > let ii = var "i" (undefined::Int)
--   > let kk = var "k" (undefined::Int)
--   > let qq = var "q" (undefined::Bool)
--   > let notE = value "not" not
--   > unfold . canonicalize . fold $ [ii,kk,notE :$ qq, notE :$ val False]
--   [x :: Int,y :: Int,not p :: Bool,not False :: Bool]
--

fold :: [Expr] -> Expr -- | O(n). Unfolds an Expr representing a list into a list of -- Exprs. This reverses the effect of fold. -- --

--   > expr [1,2,3::Int]
--   [1,2,3] :: [Int]
--   > unfold $ expr [1,2,3::Int]
--   [1 :: Int,2 :: Int,3 :: Int]
--

unfold :: Expr -> [Expr] -- | O(1). Folds a pair of Expr values into a single -- Expr. (cf. unfoldPair) -- -- This always generates an ill-typed expression. -- --

--   > foldPair (val False, val (1::Int))
--   (False,1) :: ill-typed # ExprPair $ Bool #
--

-- --

--   > foldPair (val (0::Int), val True)
--   (0,True) :: ill-typed # ExprPair $ Int #
--

-- -- This is useful when applying transformations on pairs of Exprs, -- such as canonicalize, mapValues or -- canonicalVariations. -- --

--   > let ii = var "i" (undefined::Int)
--   > let kk = var "k" (undefined::Int)
--   > unfoldPair $ canonicalize $ foldPair (ii,kk)
--   (x :: Int,y :: Int)
--

foldPair :: (Expr, Expr) -> Expr -- | O(1). Unfolds an Expr representing a pair. This reverses -- the effect of foldPair. -- --

--   > value "," ((,) :: Bool->Bool->(Bool,Bool)) :$ val True :$ val False
--   (True,False) :: (Bool,Bool)
--   > unfoldPair $ value "," ((,) :: Bool->Bool->(Bool,Bool)) :$ val True :$ val False
--   (True :: Bool,False :: Bool)
--

--   foldApp [e0]           =  e0
--   foldApp [e0,e1]        =  e0 :$ e1
--   foldApp [e0,e1,e2]     =  e0 :$ e1 :$ e2
--   foldApp [e0,e1,e2,e3]  =  e0 :$ e1 :$ e2 :$ e3
--

-- -- Remember :$ is left-associative, so: -- --

--   foldApp [e0]           =    e0
--   foldApp [e0,e1]        =   (e0 :$ e1)
--   foldApp [e0,e1,e2]     =  ((e0 :$ e1) :$ e2)
--   foldApp [e0,e1,e2,e3]  = (((e0 :$ e1) :$ e2) :$ e3)
--

-- -- This function may produce an ill-typed expression. foldApp :: [Expr] -> Expr -- | O(n). Unfold a function application Expr into a list of -- function and arguments. -- --

--   unfoldApp $ e0                    =  [e0]
--   unfoldApp $ e0 :$ e1              =  [e0,e1]
--   unfoldApp $ e0 :$ e1 :$ e2        =  [e0,e1,e2]
--   unfoldApp $ e0 :$ e1 :$ e2 :$ e3  =  [e0,e1,e2,e3]
--

-- -- Remember :$ is left-associative, so: -- --

--   unfoldApp e0                          =  [e0]
--   unfoldApp (e0 :$ e1)                  =  [e0,e1]
--   unfoldApp ((e0 :$ e1) :$ e2)          =  [e0,e1,e2]
--   unfoldApp (((e0 :$ e1) :$ e2) :$ e3)  =  [e0,e1,e2,e3]
--

unfoldApp :: Expr -> [Expr] -- | Canonicalizes an Expr so that variable names appear in order. -- Variable names are taken from the preludeNameInstances. -- --

--   > canonicalize (xx -+- yy)
--   x + y :: Int
--

-- --

--   > canonicalize (yy -+- xx)
--   x + y :: Int
--

-- --

--   > canonicalize (xx -+- xx)
--   x + x :: Int
--

-- --

--   > canonicalize (yy -+- yy)
--   x + x :: Int
--

-- -- Constants are untouched: -- --

--   > canonicalize (jj -+- (zero -+- abs' ii))
--   x + (y + abs y) :: Int
--

-- -- This also works for variable functions: -- --

--   > canonicalize (gg yy -+- ff xx -+- gg xx)
--   (f x + g y) + f y :: Int
--

canonicalize :: Expr -> Expr -- | Like canonicalize but allows customization of the list of -- variable names. (cf. lookupNames, -- variableNamesFromTemplate) -- --

--   > canonicalizeWith (const ["i","j","k","l",...]) (xx -+- yy)
--   i + j :: Int
--

-- -- The argument Expr of the argument function allows to provide a -- different list of names for different types: -- --

--   > let namesFor e
--   >   | typ e == typeOf (undefined::Char) = variableNamesFromTemplate "c1"
--   >   | typ e == typeOf (undefined::Int)  = variableNamesFromTemplate "i"
--   >   | otherwise                         = variableNamesFromTemplate "x"
--

-- --

--   > canonicalizeWith namesFor ((xx -+- ord' dd) -+- (ord' cc -+- yy))
--   (i + ord c1) + (ord c2 + j) :: Int
--

--   > canonicalization (gg yy -+- ff xx -+- gg xx)
--   [ (x :: Int,        y :: Int)
--   , (f :: Int -> Int, g :: Int -> Int)
--   , (y :: Int,        x :: Int)
--   , (g :: Int -> Int, f :: Int -> Int) ]
--

-- --

--   > canonicalization (yy -+- xx -+- yy)
--   [ (x :: Int, y :: Int)
--   , (y :: Int, x :: Int) ]
--

--   > canonicalVariations $ i_
--   [x :: Int]
--

-- --

--   > canonicalVariations $ i_ -+- i_
--   [ x + y :: Int
--   , x + x :: Int ]
--

-- --

--   > canonicalVariations $ i_ -+- i_ -+- i_
--   [ (x + y) + z :: Int
--   , (x + y) + x :: Int
--   , (x + y) + y :: Int
--   , (x + x) + y :: Int
--   , (x + x) + x :: Int ]
--

-- --

--   > canonicalVariations $ i_ -+- ord' c_
--   [x + ord c :: Int]
--

-- --

--   > canonicalVariations $ i_ -+- i_ -+- ord' c_
--   [ (x + y) + ord c :: Int
--   , (x + x) + ord c :: Int ]
--

-- --

--   > canonicalVariations $ i_ -+- i_ -+- length' (c_ -:- unit c_)
--   [ (x + y) + length (c:d:"") :: Int
--   , (x + y) + length (c:c:"") :: Int
--   , (x + x) + length (c:d:"") :: Int
--   , (x + x) + length (c:c:"") :: Int ]
--

-- -- In an expression without holes this functions just returns a singleton -- list with the expression itself: -- --

--   > canonicalVariations $ val (0 :: Int)
--   [0 :: Int]
--

-- --

--   > canonicalVariations $ ord' bee
--   [ord 'b' :: Int]
--

-- --

--   > canonicalVariations $ ii -+- jj
--   [i + j :: Int]
--

--   > fastCanonicalVariations $ i_ -+- ord' c_
--   [x + ord x :: Int]
--

-- -- Where in fact it has two, as the second x has a different -- type. Applying canonicalize disambiguates: -- --

--   > map canonicalize . fastCanonicalVariations $ i_ -+- ord' c_
--   [x + ord c :: Int]
--

--   > let zero = val (0::Int)
--   > let one  = val (1::Int)
--   > let xx   = var "x" (undefined :: Int)
--   > let yy   = var "y" (undefined :: Int)
--   > let e1 -+- e2  =  value "+" ((+)::Int->Int->Int) :$ e1 :$ e2
--

-- --

--   > (zero -+- one) `match` (xx -+- yy)
--   Just [(y :: Int,1 :: Int),(x :: Int,0 :: Int)]
--

-- --

--   > (zero -+- (one -+- two)) `match` (xx -+- yy)
--   Just [(y :: Int,1 + 2 :: Int),(x :: Int,0 :: Int)]
--

-- --

--   > (zero -+- (one -+- two)) `match` (xx -+- (yy -+- yy))
--   Nothing
--

-- -- In short: -- --

--             (zero -+- one) `match` (xx -+- yy)           =  Just [(xx,zero), (yy,one)]
--   (zero -+- (one -+- two)) `match` (xx -+- yy)           =  Just [(xx,zero), (yy,one-+-two)]
--   (zero -+- (one -+- two)) `match` (xx -+- (yy -+- yy))  =  Nothing
--

match :: Expr -> Expr -> Maybe [(Expr, Expr)] -- | Like match but allowing predefined bindings. -- --

--   matchWith [(xx,zero)] (zero -+- one) (xx -+- yy)  =  Just [(xx,zero), (yy,one)]
--   matchWith [(xx,one)]  (zero -+- one) (xx -+- yy)  =  Nothing
--

--   > let zero = val (0::Int)
--   > let one  = val (1::Int)
--   > let xx   = var "x" (undefined :: Int)
--   > let yy   = var "y" (undefined :: Int)
--   > let e1 -+- e2  =  value "+" ((+)::Int->Int->Int) :$ e1 :$ e2
--

-- --

--    one `isInstanceOf` one   =  True
--     xx `isInstanceOf` xx    =  True
--     yy `isInstanceOf` xx    =  True
--   zero `isInstanceOf` xx    =  True
--     xx `isInstanceOf` zero  =  False
--    one `isInstanceOf` zero  =  False
--     (xx -+- (yy -+- xx)) `isInstanceOf`   (xx -+- yy)  =  True
--     (yy -+- (yy -+- xx)) `isInstanceOf`   (xx -+- yy)  =  True
--   (zero -+- (yy -+- xx)) `isInstanceOf` (zero -+- yy)  =  True
--    (one -+- (yy -+- xx)) `isInstanceOf` (zero -+- yy)  =  False
--

--   > (xx -+- yy) `isSubexprOf` (zz -+- (xx -+- yy))
--   True
--

-- --

--   > (xx -+- yy) `isSubexprOf` abs' (yy -+- xx)
--   False
--

-- --

--   > xx `isSubexprOf` yy
--   False
--

isSubexprOf :: Expr -> Expr -> Bool -- | Express typeclass instances provide an expr function -- that allows values to be deeply encoded as applications of -- Exprs. -- --

--   expr False  =  val False
--   expr (Just True)  =  value "Just" (Just :: Bool -> Maybe Bool) :$ val True
--

-- -- The function expr can be contrasted with the function -- val: -- --

val always encodes values as atomic Value -- Exprs -- shallow encoding.
expr ideally encodes expressions as applications -- (:$) between Value Exprs -- deep encoding.

--   data Stack a = Stack a (Stack a) | Empty
--

-- --

--   instance Express a => Express (Stack a) where
--     expr s@(Stack x y) = value "Stack" (Stack ->>: s) :$ expr x :$ expr y
--     expr s@Empty       = value "Empty" (Empty   -: s)
--

-- -- To declare expr it may be useful to use auxiliary type binding -- operators: -:, ->:, ->>:, -- ->>>:, ->>>>:, -- ->>>>>:, ... -- -- For types with atomic values, just declare expr = val class Typeable a => Express a expr :: Express a => a -> Expr -- | Derives an Express instance for the given type Name. -- -- This function needs the TemplateHaskell extension. -- -- If -:, ->:, ->>:, ->>>:, -- ... are not in scope, this will derive them as well. deriveExpress :: Name -> DecsQ -- | Derives a Express instance for a given type Name -- cascading derivation of type arguments as well. deriveExpressCascading :: Name -> DecsQ -- | Same as deriveExpress but does not warn when instance already -- exists (deriveExpress is preferable). deriveExpressIfNeeded :: Name -> DecsQ -- | If we were to come up with a variable name for the given type what -- name would it be? -- -- An instance for a given type Ty is simply given by: -- --

--   instance Name Ty where name _ = "x"
--

-- -- Examples: -- --

--   > name (undefined :: Int)
--   "x"
--

-- --

--   > name (undefined :: Bool)
--   "p"
--

-- --

--   > name (undefined :: [Int])
--   "xs"
--

-- -- This is then used to generate an infinite list of variable -- names: -- --

--   > names (undefined :: Int)
--   ["x", "y", "z", "x'", "y'", "z'", "x''", "y''", "z''", ...]
--

-- --

--   > names (undefined :: Bool)
--   ["p", "q", "r", "p'", "q'", "r'", "p''", "q''", "r''", ...]
--

-- --

--   > names (undefined :: [Int])
--   ["xs", "ys", "zs", "xs'", "ys'", "zs'", "xs''", "ys''", ...]
--

class Name a -- | O(1). -- -- Returns a name for a variable of the given argument's type. -- --

--   > name (undefined :: Int)
--   "x"
--

-- --

--   > name (undefined :: [Bool])
--   "ps"
--

-- --

--   > name (undefined :: [Maybe Integer])
--   "mxs"
--

-- -- The default definition is: -- --

--   name _ = "x"
--

name :: Name a => a -> String -- | Returns na infinite list of variable names from the given type: the -- result of variableNamesFromTemplate after name. -- --

--   > names (undefined :: Int)
--   ["x", "y", "z", "x'", "y'", "z'", "x''", "y''", "z''", ...]
--

-- --

--   > names (undefined :: Bool)
--   ["p", "q", "r", "p'", "q'", "r'", "p''", "q''", "r''", ...]
--

-- --

--   > names (undefined :: [Int])
--   ["xs", "ys", "zs", "xs'", "ys'", "zs'", "xs''", "ys''", ...]
--

names :: Name a => a -> [String] -- | Returns an infinite list of variable names based on the given -- template. -- --

--   > variableNamesFromTemplate "x"
--   ["x", "y", "z", "x'", "y'", ...]
--

-- --

--   > variableNamesFromTemplate "p"
--   ["p", "q", "r", "p'", "q'", ...]
--

-- --

--   > variableNamesFromTemplate "xy"
--   ["xy", "zw", "xy'", "zw'", "xy''", ...]
--

variableNamesFromTemplate :: String -> [String] -- | Derives a Name instance for the given type Name. -- -- This function needs the TemplateHaskell extension. deriveName :: Name -> DecsQ -- | Derives a Name instance for a given type Name cascading -- derivation of type arguments as well. deriveNameCascading :: Name -> DecsQ -- | Same as deriveName but does not warn when instance already -- exists (deriveName is preferable). deriveNameIfNeeded :: Name -> DecsQ -- | O(1). Reifies an Eq instance into a list of -- Exprs. The list will contain == and /= for the -- given type. (cf. mkEq, mkEquation) -- --

--   > reifyEq (undefined :: Int)
--   [ (==) :: Int -> Int -> Bool
--   , (/=) :: Int -> Int -> Bool ]
--

-- --

--   > reifyEq (undefined :: Bool)
--   [ (==) :: Bool -> Bool -> Bool
--   , (/=) :: Bool -> Bool -> Bool ]
--

-- --

--   > reifyEq (undefined :: String)
--   [ (==) :: [Char] -> [Char] -> Bool
--   , (/=) :: [Char] -> [Char] -> Bool ]
--

--   > reifyOrd (undefined :: Int)
--   [ (<=) :: Int -> Int -> Bool
--   , (<) :: Int -> Int -> Bool ]
--

-- --

--   > reifyOrd (undefined :: Bool)
--   [ (<=) :: Bool -> Bool -> Bool
--   , (<) :: Bool -> Bool -> Bool ]
--

-- --

--   > reifyOrd (undefined :: [Bool])
--   [ (<=) :: [Bool] -> [Bool] -> Bool
--   , (<) :: [Bool] -> [Bool] -> Bool ]
--

--   > reifyName (undefined :: Int)
--   [name :: Int -> [Char]]
--

-- --

--   > reifyName (undefined :: Bool)
--   [name :: Bool -> [Char]]
--

reifyName :: (Typeable a, Name a) => a -> [Expr] -- | O(1). Builds a reified Eq instance from the given -- == function. (cf. reifyEq) -- --

--   > mkEq ((==) :: Int -> Int -> Bool)
--   [ (==) :: Int -> Int -> Bool
--   , (/=) :: Int -> Int -> Bool ]
--

--   > isEq (reifyEqOrd (undefined :: Int)) (val (0::Int))
--   True
--

-- --

--   > isEq (reifyEqOrd (undefined :: Int)) (val ([[[0::Int]]]))
--   False
--

--   > isOrd (reifyEqOrd (undefined :: Int)) (val (0::Int))
--   True
--

-- --

--   > isOrd (reifyEqOrd (undefined :: Int)) (val ([[[0::Int]]]))
--   False
--

--   > isEqT (reifyEqOrd (undefined :: Int)) (typeOf (undefined :: Int))
--   True
--

-- --

--   > isEqT (reifyEqOrd (undefined :: Int)) (typeOf (undefined :: [[[Int]]]))
--   False
--

--   > isOrdT (reifyEqOrd (undefined :: Int)) (typeOf (undefined :: Int))
--   True
--

-- --

--   > isOrdT (reifyEqOrd (undefined :: Int)) (typeOf (undefined :: [[[Int]]]))
--   False
--

-- -- Given that the instances list has length n, this function is -- O(n). isOrdT :: [Expr] -> TypeRep -> Bool -- | O(n). Returns whether both Eq and Ord instance -- exist in the given list for the given TypeRep. -- -- Given that the instances list has length n, this function is -- O(n). isEqOrdT :: [Expr] -> TypeRep -> Bool mkEquation :: [Expr] -> Expr -> Expr -> Expr mkComparisonLE :: [Expr] -> Expr -> Expr -> Expr mkComparisonLT :: [Expr] -> Expr -> Expr -> Expr mkComparison :: String -> [Expr] -> Expr -> Expr -> Expr lookupComparison :: String -> TypeRep -> [Expr] -> Maybe Expr listVarsWith :: [Expr] -> Expr -> [Expr] lookupName :: [Expr] -> Expr -> String lookupNames :: [Expr] -> Expr -> [String] validApps :: [Expr] -> Expr -> [Expr] findValidApp :: [Expr] -> Expr -> Maybe Expr preludeNameInstances :: [Expr] -- | Defines some Expr fixtures to facilitate testing and playing -- around on the REPL (GHCI). -- --

Instead of having to write:

> value "&&"
--   (&&) :$ (value "not" not :$ val True) :$ val False not True
--   && False :: Bool

Using this module, we can just -- write:

> not' true -&&- false not True && False
--   :: Bool

Instead of having to write:

> value "+"
--   ((+)::Int->Int->Int) :$ (value "*" ((*)::Int->Int->Int) :$
--   var "x" (undefined::Int) :$ var "y" (undefined::Int)) :$ (value "*"
--   ((*)::Int->Int->Int) :$ val (1::Int) :$ val (2::Int)) x * y + 1
--   * 2 :: Int

Using this module, we can just write:

> xx -*-
--   yy -+- one -*- two x * y + 1 * 2 :: Int

Instead of having to write:

> value "||" (||) :$ (value
--   "==" ((==)::Int->Int->Bool) :$ val (3::Int) :$ (value "+"
--   ((+)::Int->Int->Int) :$ var "y" (undefined::Int) :$ val
--   (1::Int))) :$ (value "not" not :$ val False) 3 == y + 1 || not False
--   :: Bool

We can just write:

> (three -==- yy -+- one) -||-
--   not' false x == y + 1 || not False :: Bool

-- -- This exports over a hundred symbols to be used mainly when writing -- unit tests or playing around on GHCi. -- -- Since the Expr type only allows monomorphic values, encoded -- polimorphic values are monomorphized usually to the Int type. -- -- Beware: lifted Expr functions sometimes work for -- different types. The current version does not have a rationale for -- types that are included: you have to either try around on the REPL or -- look at the source to really know. module Data.Express.Fixtures -- | Expr representing a hole of Bool type. -- --

--   > b_
--   _ :: Bool
--

b_ :: Expr -- | Expr representing a variable p :: Bool. -- --

--   > pp
--   p :: Bool
--

pp :: Expr -- | Expr representing a variable q :: Bool. -- --

--   > qq
--   q :: Bool
--

qq :: Expr -- | Expr representing a variable r :: Bool. -- --

--   > rr
--   r :: Bool
--

rr :: Expr -- | Expr representing a variable p' :: Bool. -- --

--   > pp'
--   p' :: Bool
--

pp' :: Expr -- | False encoded as an Expr. -- --

--   > false
--   False :: Bool
--

false :: Expr -- | True encoded as an Expr. -- --

--   > true
--   True :: Bool
--

true :: Expr -- | The function not encoded as an Expr. -- --

--   > notE
--   not :: Bool -> Bool
--

notE :: Expr -- | The function or encoded as an Expr. -- --

--   > orE
--   (||) :: Bool -> Bool -> Bool
--

orE :: Expr -- | The function and encoded as an Expr. -- --

--   > andE
--   (&&) :: Bool -> Bool -> Bool
--

andE :: Expr implies :: Expr -- | The function not lifted over the Expr type. -- --

--   > not' false
--   not False :: Bool
--

-- --

--   > evalBool $ not' false
--   True
--

-- --

--   > not' pp
--   not p :: Bool
--

not' :: Expr -> Expr -- | The function || lifted over the Expr type. -- --

--   > pp -||- qq
--   p || q :: Bool
--

-- --

--   > false -||- true
--   False || True :: Bool
--

-- --

--   > evalBool $ false -||- true
--   True
--

(-||-) :: Expr -> Expr -> Expr -- | The function && lifted over the Expr type. -- --

--   > pp -&&- qq
--   p && q :: Bool
--

-- --

--   > false -&&- true
--   False && True :: Bool
--

-- --

--   > evalBool $ false -&&- true
--   False
--

(-&&-) :: Expr -> Expr -> Expr (-==>-) :: Expr -> Expr -> Expr (-==-) :: Expr -> Expr -> Expr infix 4 -==- (-/=-) :: Expr -> Expr -> Expr infix 4 -/=- (-<=-) :: Expr -> Expr -> Expr infix 4 -<=- (-<-) :: Expr -> Expr -> Expr infix 4 -<- compare' :: Expr -> Expr -> Expr -- | A typed hole of Int type. -- --

--   > i_
--   _ :: Int
--

i_ :: Expr -- | A variable x of Int type. -- --

--   > xx
--   x :: Int
--

xx :: Expr -- | A variable y of Int type. -- --

--   > yy
--   y :: Int
--

yy :: Expr -- | A variable z of Int type. -- --

--   > zz
--   z :: Int
--

zz :: Expr -- | A variable x' of Int type. -- --

--   > xx'
--   x' :: Int
--

xx' :: Expr ii :: Expr jj :: Expr kk :: Expr ii' :: Expr -- | The value 0 bound to the Int type encoded as an -- Expr. -- --

--   > zero
--   0 :: Int
--

zero :: Expr -- | The value 1 bound to the Int type encoded as an -- Expr. -- --

--   > one
--   1 :: Int
--

one :: Expr -- | The value 2 bound to the Int type encoded as an -- Expr. -- --

--   > two
--   2 :: Int
--

two :: Expr -- | The value 3 bound to the Int type encoded as an -- Expr. -- --

--   > three
--   3 :: Int
--

three :: Expr -- | The value -1 bound to the Int type encoded as an -- Expr. -- --

--   > minusOne
--   -1 :: Int
--

minusOne :: Expr -- | The value -2 bound to the Int type encoded as an -- Expr. -- --

--   > minusOne
--   -2 :: Int
--

minusTwo :: Expr -- | The function id for the Int type encoded as an -- Expr. (See also id'.) -- --

--   > idE :$ xx
--   id x :: Int
--

-- --

--   > idE :$ zero
--   id 0 :: Int
--

-- --

--   > evaluate $ idE :$ zero :: Maybe Int
--   Just 0
--

idE :: Expr -- | negate over the Int type encoded as an Expr -- --

--   > negateE
--   negate :: Int -> Int
--

negateE :: Expr -- | abs over the Int type encoded as an Expr. -- --

--   > absE
--   abs :: Int -> Int
--

absE :: Expr -- | The function id encoded as an Expr. (cf. id') idInt :: Expr -- | The function id encoded as an Expr. (cf. id') idBool :: Expr -- | The function id encoded as an Expr. (cf. id') idChar :: Expr -- | The function id encoded as an Expr. (cf. id') idInts :: Expr -- | The function id encoded as an Expr. (cf. id') idBools :: Expr -- | The function id encoded as an Expr. (cf. id') idString :: Expr -- | Constructs an application of id as an Expr. Only works -- for Int, Bool, Char, String, -- [Int], [Bool]. -- --

--   > id' yy
--   id yy :: Int
--

-- --

--   > id' one
--   id 1 :: Int
--

-- --

--   > evl (id' one) :: Int
--   1
--

-- --

--   > id' pp
--   id p :: Bool
--

-- --

--   > id' false
--   id' False :: Bool
--

-- --

--   > evl (id' true) :: Bool
--   True :: Bool
--

id' :: Expr -> Expr const' :: Expr -> Expr -> Expr -- | negate over the Int type lifted over the Expr -- type. -- --

--   > negate' xx
--   negate x :: Int
--

-- --

--   > evl (negate' one) :: Int
--   -1
--

negate' :: Expr -> Expr -- | abs over the Int type lifted over the Expr type. -- --

--   > abs' xx'
--   abs x' :: Int
--

-- --

--   > evl (abs' minusTwo) :: Int
--   2
--

abs' :: Expr -> Expr -- | The operator + for the Int type. (See also -+-.) -- --

--   > plus
--   (+) :: Int -> Int -> Int
--

-- --

--   > plus :$ one
--   (1 +) :: Int -> Int
--

-- --

--   > plus :$ xx :$ yy
--   x + y :: Int
--

plus :: Expr -- | The operator * for the Int type. (See also -*-.) -- --

--   > times
--   (*) :: Int -> Int -> Int
--

-- --

--   > times :$ two
--   (2 *) :: Int -> Int
--

-- --

--   > times :$ xx :$ yy
--   x * y :: Int
--

times :: Expr -- | The operator + for the Int type for use on Exprs. -- (See also plus.) -- --

--   > two -+- three
--   2 + 3 :: Int
--

-- --

--   > minusOne -+- minusTwo -+- zero
--   ((-1) + (-2)) + 0 :: Int
--

-- --

--   > xx -+- (yy -+- zz)
--   x + (y + z) :: Int
--

(-+-) :: Expr -> Expr -> Expr infixl 6 -+- -- | The operator * for the Int type lifted over the -- Expr type. (See also times.) -- --

--   > three -*- three
--   9 :: Int
--

-- --

--   > one -*- two -*- three
--   (1 * 2) * 3 :: Int
--

-- --

--   > two -*- xx
--   2 * x :: Int
--

(-*-) :: Expr -> Expr -> Expr -- | A variable function f of 'Int -> Int' type lifted over the -- Expr type. -- --

--   > ff xx
--   f x :: Int
--

-- --

--   > ff one
--   f 1 :: Int
--

ff :: Expr -> Expr -- | A variable f of 'Int -> Int' type encoded as an -- Expr. -- --

--   > ffE
--   f :: Int -> Int
--

ffE :: Expr -- | A variable function g of 'Int -> Int' type lifted over the -- Expr type. -- --

--   > gg yy
--   g y :: Int
--

-- --

--   > gg minusTwo
--   gg (-2) :: Int
--

gg :: Expr -> Expr -- | A variable g of 'Int -> Int' type encoded as an -- Expr. -- --

--   > ggE
--   g :: Int -> Int
--

ggE :: Expr -- | A variable binary operator ? lifted over the Expr -- type. Works for Int, Bool, Char, [Int] -- and String. -- --

--   > xx -?- yy
--   x ? y :: Int
--

-- --

--   > pp -?- qq
--   p ? q :: Bool
--

-- --

--   > xx -?- qq
--   *** Exception: (-?-): cannot apply `(?) :: * -> * -> *` to `x :: Int' and `q :: Bool'.  Unhandled types?
--

(-?-) :: Expr -> Expr -> Expr (-$-) :: Expr -> Expr -> Expr infixl 6 -$- odd' :: Expr -> Expr even' :: Expr -> Expr -- | A hole of Char type encoded as an Expr. -- --

--   > c_
--   _ :: Char
--

c_ :: Expr cc :: Expr dd :: Expr ccs :: Expr ae :: Expr -- | The character 'b' encoded as an Expr -- --

--   > bee
--   'b' :: Char
--

-- --

--   > evl bee :: Char
--   'b'
--

bee :: Expr -- | The character 'c' encoded as an Expr -- --

--   > cee
--   'c' :: Char
--

-- --

--   > evl cee :: Char
--   'c'
--

cee :: Expr -- | The character 'd' encoded as an Expr -- --

--   > dee
--   'd' :: Char
--

-- --

--   > evl dee :: Char
--   'd'
--

dee :: Expr space :: Expr lineBreak :: Expr ord' :: Expr -> Expr ordE :: Expr -- | A typed hole of [Int] type encoded as an Expr. -- --

--   > is_
--   _ :: [Int]
--

is_ :: Expr -- | A variable named xs of type [Int] encoded as an -- Expr. -- --

--   > xxs
--   xs :: [Int]
--

xxs :: Expr -- | A variable named ys of type [Int] encoded as an -- Expr. -- --

--   > yys
--   ys :: [Int]
--

yys :: Expr -- | An empty list of type [Int] encoded as an Expr. -- --

--   > nil
--   [] :: [Int]
--

nil :: Expr -- | An empty String encoded as an Expr. -- --

--   > emptyString
--   "" :: String
--

emptyString :: Expr -- | The empty list '[]' encoded as an Expr. nilInt :: Expr -- | The empty list '[]' encoded as an Expr. nilBool :: Expr -- | The empty list '[]' encoded as an Expr. nilChar :: Expr -- | The list constructor with Int as element type encoded as an -- Expr. -- --

--   > cons
--   (:) :: Int -> [Int] -> [Int]
--

-- --

--   > cons :$ one :$ nil
--   [1] :: [Int]
--

-- -- Consider using -:- and unit when building lists of -- Expr. cons :: Expr -- | The list constructor : encoded as an Expr. consInt :: Expr -- | The list constructor : encoded as an Expr. consBool :: Expr -- | The list constructor : encoded as an Expr. consChar :: Expr -- | The list constructor lifted over the Expr type. Works for the -- element types Int, Char and Bool. -- --

--   > zero -:- one -:- unit two
--   [0,1,2] :: [Int]
--

-- --

--   > zero -:- one -:- two -:- nil
--   [0,1,2] :: [Int]
--

-- --

--   > bee -:- unit cee
--   "bc" :: [Char]
--

(-:-) :: Expr -> Expr -> Expr infixr 5 -:- -- | unit constructs a list with a single element. This works for -- elements of type Int, Char and Bool. -- --

--   > unit one
--   [1]
--

-- --

--   > unit false
--   [False]
--

unit :: Expr -> Expr -- | List concatenation lifted over the Expr type. Works for the -- element types Int, Char and Bool. -- --

--   > (zero -:- one -:- nil) -:- (two -:- three -:- nil)
--   [0,1] -++- [2,3] :: [Int]
--

-- --

--   > (bee -:- unit cee) -:- unit dee
--   "bc" -++- "c" :: [Char]
--

(-++-) :: Expr -> Expr -> Expr infixr 5 -++- -- | List head lifted over the Expr type. Works for the -- element types Int, Char and Bool. -- --

--   > head' $ unit one
--   head [1] :: Int
--

-- --

--   > head' $ unit bee
--   head "b" :: Char
--

-- --

--   > head' $ zero -:- unit two
--   head [0,2] :: Int
--

-- --

--   > evl $ head' $ unit one :: Int
--   1
--

head' :: Expr -> Expr -- | List tail lifted over the Expr type. Works for the -- element types Int, Char and Bool. -- --

--   > tail' $ unit one
--   tail [1] :: [Int]
--

-- --

--   > tail' $ unit bee
--   tail "b" :: [Char]
--

-- --

--   > tail' $ zero -:- unit two
--   tail [0,2] :: [Int]
--

-- --

--   > evl $ tail' $ zero -:- unit two :: [Int]
--   [2]
--

tail' :: Expr -> Expr -- | List length lifted over the Expr type. Works for the -- element types Int, Char and Bool. -- --

--   > length' $ unit one
--   length [1] :: Int
--

-- --

--   > length' $ unit bee
--   length "b" :: Int
--

-- --

--   > length' $ zero -:- unit two
--   length [0,2] :: Int
--

-- --

--   > evl $ length' $ unit one :: Int
--   1
--

length' :: Expr -> Expr elem' :: Expr -> Expr -> Expr sort' :: Expr -> Expr insert' :: Expr -> Expr -> Expr nothing :: Expr nothingInt :: Expr nothingBool :: Expr just :: Expr -> Expr justInt :: Expr justBool :: Expr comma :: Expr pair :: Expr -> Expr -> Expr (-|-) :: Expr -> Expr -> Expr triple :: Expr -> Expr -> Expr -> Expr quadruple :: Expr -> Expr -> Expr -> Expr -> Expr quintuple :: Expr -> Expr -> Expr -> Expr -> Expr -> Expr sixtuple :: Expr -> Expr -> Expr -> Expr -> Expr -> Expr -> Expr