-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Dynamically-typed expressions involving function application and variables.
--
-- Express is a library for manipulating dynamically typed Haskell
-- expressions. It's like Data.Dynamic but with support for
-- encoding function aplication 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 1.0.2
-- | 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]
-- | Like nubSort but allows providing a function to compare
-- values.
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
-- | Merges two lists discarding repeated elements.
--
-- The argument lists need to be in order.
--
--
-- > [1,10,100] +++ [9,10,11]
-- [1,9,10,11,100]
--
(+++) :: 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
-- | Returns the operator precedence of an infix string.
--
--
-- > outernmostPrec "1 + 2"
-- Just 6
--
outernmostPrec :: String -> Maybe Int
-- | Returns whether the given String represents a negative literal.
--
--
-- > isNegativeLiteral "1"
-- False
-- > isNegativeLiteral "-1"
-- True
-- > isNegativeLiteral "-x"
-- False
-- > isNegativeLiteral "1 - 3"
-- False
--
isNegativeLiteral :: String -> Bool
-- | Check if a function / operator is infix
--
--
-- isInfix "foo" == False
-- isInfix "(+)" == False
-- isInfix "`foo`" == True
-- isInfix "+" == True
--
isInfix :: String -> Bool
-- | Is the given string a prefix function?
--
--
-- > isPrefix "abs"
-- True
--
--
--
-- > isPrefix "+"
-- False
--
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]
-- | Cycles through a list of variable names priming them at each
-- iteration.
--
--
-- primeCycle ["x","y","z"]
--
--
--
--
-- - "x","y","z","x'","y'","z'","x''","y''","z''","x'''",...
--
primeCycle :: [String] -> [String]
-- | Re-exports a few standard Haskell modules module along with additional
-- functions.
module Data.Express.Utils
-- | 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]
-- | Normalizes a type by applying it to necessary type variables making it
-- accept zero type parameters. The normalized type is paired with a list
-- of necessary type variables.
--
--
-- > putStrLn $(stringE . show =<< normalizeType ''Int)
-- (ConT ''Int, [])
--
--
--
-- > putStrLn $(stringE . show =<< normalizeType ''Maybe)
-- (AppT (ConT ''Maybe) (VarT ''a),[VarT ''a])
--
--
--
-- > putStrLn $(stringE . show =<< normalizeType ''Either)
-- (AppT (AppT (ConT ''Either) (VarT ''a)) (VarT ''b),[VarT ''a,VarT ''b])
--
--
--
-- > putStrLn $(stringE . show =<< normalizeType ''[])
-- (AppT (ConT ''[]) (VarT a),[VarT a])
--
normalizeType :: Name -> Q (Type, [Type])
-- | Normalizes a type by applying it to units to make it star-kinded. (cf.
-- normalizeType)
normalizeTypeUnits :: Name -> Q Type
-- | Given a type name and a class name, returns whether the type is an
-- instance of that class. The given type must be star-kinded ( *
-- ) and the given class double-star-kinded ( * -> * .
--
--
-- > putStrLn $(stringE . show =<< ''Int `isInstanceOf` ''Num)
-- True
--
--
--
-- > putStrLn $(stringE . show =<< ''Int `isInstanceOf` ''Fractional)
-- False
--
isInstanceOf :: Name -> Name -> Q Bool
-- | The negation of isInstanceOf.
isntInstanceOf :: Name -> Name -> Q Bool
-- | Given a type name, return the number of arguments taken by that type.
-- Examples in partially broken TH:
--
--
-- > putStrLn $(stringE . show =<< typeArity ''Int)
-- 0
--
--
--
-- > putStrLn $(stringE . show =<< typeArity ''Maybe)
-- 1
--
--
--
-- > putStrLn $(stringE . show =<< typeArity ''Either)
-- 2
--
--
--
-- > putStrLn $(stringE . show =<< typeArity ''[])
-- 1
--
--
--
-- > putStrLn $(stringE . show =<< typeArity ''(,))
-- 2
--
--
--
-- > putStrLn $(stringE . show =<< typeArity ''(,,))
-- 3
--
--
--
-- > putStrLn $(stringE . show =<< typeArity ''String)
-- 0
--
--
-- This works for Data's and Newtype's and it is useful when generating
-- typeclass instances.
typeArity :: Name -> Q Int
-- | Given a type Name, returns a list of its type constructor
-- Names paired with the type arguments they take. the type
-- arguments they take.
--
--
-- > putStrLn $(stringE . show =<< typeConstructors ''Bool)
-- [ ('False, [])
-- , ('True, [])
-- ]
--
--
--
-- > putStrLn $(stringE . show =<< typeConstructors ''[])
-- [ ('[], [])
-- , ('(:), [VarT ''a, AppT ListT (VarT ''a)])
-- ]
--
--
--
-- > putStrLn $(stringE . show =<< typeConstructors ''(,))
-- [('(,), [VarT (mkName "a"), VarT (mkName "b")])]
--
--
--
-- > data Point = Pt Int Int
-- > putStrLn $(stringE . show =<< typeConstructors ''Point)
-- [('Pt,[ConT ''Int, ConT ''Int])]
--
typeConstructors :: Name -> Q [(Name, [Type])]
-- | Is the given Name a type synonym?
--
--
-- > putStrLn $(stringE . show =<< isTypeSynonym 'show)
-- False
--
--
--
-- > putStrLn $(stringE . show =<< isTypeSynonym ''Char)
-- False
--
--
--
-- > putStrLn $(stringE . show =<< isTypeSynonym ''String)
-- True
--
isTypeSynonym :: Name -> Q Bool
-- | Resolves a type synonym.
--
--
-- > putStrLn $(stringE . show =<< typeSynonymType ''String)
-- AppT ListT (ConT ''Char)
--
typeSynonymType :: Name -> Q Type
mergeIFns :: DecsQ -> DecsQ
mergeI :: DecsQ -> DecsQ -> DecsQ
-- | Lookups the name of a value throwing an error when it is not found.
--
--
-- > putStrLn $(stringE . show =<< lookupValN "show")
-- 'show
--
lookupValN :: String -> Q Name
-- | Encodes a Name as a String. This is useful when
-- generating error messages.
--
--
-- > showJustName ''Int
-- "Int"
--
--
--
-- > showJustName ''String
-- "String"
--
--
--
-- > showJustName ''Maybe
-- "Maybe"
--
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
-- | Returns the functional arity of the given TypeRep.
--
--
-- > tyArity $ typeOf (undefined :: Int)
-- 0
--
--
--
-- > tyArity $ typeOf (undefined :: Int -> Int)
-- 1
--
--
--
-- > tyArity $ typeOf (undefined :: (Int,Int))
-- 0
--
tyArity :: TypeRep -> Int
-- | Deconstructs a functional TypeRep into a pair of
-- TypeReps.
--
--
-- > unFunTy $ typeOf (undefined :: Int -> Char -> Bool)
-- (Int,Char -> Bool)
--
--
-- This function raises an error on non-functional types.
--
-- (cf. argumentTy and resultTy)
unFunTy :: TypeRep -> (TypeRep, TypeRep)
-- | Returns whether a TypeRep is functional.
--
--
-- > isFunTy $ typeOf (undefined :: Int -> Int)
-- True
-- > isFunTy $ typeOf (undefined :: Int)
-- False
--
isFunTy :: TypeRep -> Bool
-- | Returns the argument TypeRep of a given functional
-- TypeRep.
--
--
-- argumentTy $ typeOf (undefined :: Int -> Char)
-- Int
--
--
-- This function raises an error on non-functional types.
--
-- (cf. resultTy)
argumentTy :: TypeRep -> TypeRep
-- | Returns the result TypeRep of a given functional
-- TypeRep.
--
--
-- > resultTy $ typeOf (undefined :: Int -> Char)
-- Char
--
--
--
-- > resultTy $ typeOf (undefined :: Int -> Char -> Bool)
-- Char -> Bool
--
--
-- This function raises an error on non-functional types.
--
-- (cf. argumentTy and finalResultTy)
resultTy :: TypeRep -> TypeRep
-- | Returns the ultimate result type of the given TypeRep.
--
--
-- > finalResultTy (typeOf (undefined :: Int))
-- Int
--
--
--
-- > finalResultTy (typeOf (undefined :: Int -> Char))
-- Char
--
--
--
-- > finalResultTy (typeOf (undefined :: Int -> Char -> Bool))
-- Bool
--
finalResultTy :: TypeRep -> TypeRep
-- | The Bool type encoded as a TypeRep.
boolTy :: TypeRep
-- | The Int type encoded as a TypeRep.
intTy :: TypeRep
-- | The Ordering type encoded as a TypeRep.
orderingTy :: TypeRep
-- | Constructs a comparison type ( a -> a -> Bool ) from
-- the given argument type.
--
--
-- > mkComparisonTy $ typeOf (undefined :: Int)
-- Int -> Int -> Bool
--
--
--
-- > mkComparisonTy $ typeOf (undefined :: ())
-- () -> () -> Bool
--
mkComparisonTy :: TypeRep -> TypeRep
-- | Constructs a "compare" type ( a -> a -> Ordering ) from
-- the given argument type.
--
--
-- > mkCompareTy $ typeOf (undefined :: Int)
-- Int -> Int -> Ordering
--
--
--
-- > mkCompareTy $ typeOf (undefined :: ())
-- () -> () -> Ordering
--
mkCompareTy :: TypeRep -> TypeRep
-- | The function type constructor as a TyCon
funTyCon :: TyCon
-- | Compares two TypeReps.
--
-- Different versions of Typeable/GHC provide different orderings for
-- TypeReps. The following is a version independent ordering, with
-- the following properties:
--
--
-- - functional types with more arguments are larger;
-- - type constructors with more arguments are larger.
--
--
--
-- > typeOf (undefined :: Int -> Int) `compareTy` typeOf (undefined :: () -> () -> ())
-- LT
--
--
--
-- > typeOf (undefined :: Int) `compareTy` typeOf (undefined :: ())
-- GT
--
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]
-- | Returns types and subtypes from the given list of TypeReps.
--
--
-- > typesInList [typeOf (undefined :: () -> Int), typeOf (undefined :: String -> String -> Bool)]
-- [(),Bool,Char,Int,[Char],() -> Int,[Char] -> Bool,[Char] -> [Char] -> Bool]
--
--
--
-- > typesInList [typeOf (undefined :: (Char,Int))]
-- [Char,Int,(Char,Int)]
--
typesInList :: [TypeRep] -> [TypeRep]
-- | Return the number of outer list nestings in a TypeRep
--
--
-- > countListTy $ typeOf (undefined :: Int)
-- 0
--
--
--
-- > countListTy $ typeOf (undefined :: [Bool])
-- 1
--
--
--
-- > countListTy $ typeOf (undefined :: [[()]])
-- 2
--
--
--
-- > countListTy $ typeOf (undefined :: String)
-- 1
--
--
--
-- > countListTy $ typeOf (undefined :: ([Int],[Bool]))
-- 0
--
countListTy :: TypeRep -> Int
-- | 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 with
-- $$.
--
--
-- > 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 :: 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 :: 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). Returns whether the given Expr is of a functional
-- type. This is the same as checking if the arity of the given
-- Expr is non-zero.
--
--
-- > isFun (value "abs" (abs :: Int -> Int))
-- True
--
--
--
-- > isFun (val (1::Int))
-- False
--
--
--
-- > isFun (value "const" (const :: Bool -> Bool -> Bool) :$ val False)
-- True
--
isFun :: 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
--
--
-- This comparison is not a total order.
compareComplexity :: Expr -> Expr -> Ordering
-- | O(n). Lexicographical structural comparison of Exprs
-- where variables < constants < applications then types are
-- compared before string representations.
--
--
-- > compareLexicographically one (one -+- one)
-- LT
-- > compareLexicographically one zero
-- GT
-- > compareLexicographically (xx -+- zero) (zero -+- xx)
-- LT
-- > compareLexicographically (zero -+- xx) (zero -+- xx)
-- EQ
--
--
-- (cf. compareTy)
--
-- This comparison is a total order.
compareLexicographically :: Expr -> Expr -> Ordering
-- | O(n). A fast total order between Exprs that can be used
-- when sorting Expr values.
--
-- This is lazier than its counterparts compareComplexity and
-- compareLexicographically and tries to evaluate the given
-- Exprs as least as possible.
compareQuickly :: 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^3) 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
-- ]
--
--
-- Runtime averages to O(n^2 log n) on evenly distributed
-- expressions such as (f x + g y) + (h z + f w); and to
-- O(n^3) on deep expressions such as f (g (h (f (g (h
-- x))))).
nubSubexprs :: Expr -> [Expr]
-- | O(n^2). 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
-- ]
--
--
-- Runtime averages to O(n log n) on evenly distributed
-- expressions such as (f x + g y) + (h z + f w); and to
-- O(n^2) on deep expressions such as f (g (h (f (g (h
-- x))))).
nubValues :: Expr -> [Expr]
-- | O(n^2). 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]
--
--
-- Runtime averages to O(n log n) on evenly distributed
-- expressions such as (f x + g y) + (h z + f w); and to
-- O(n^2) on deep expressions such as f (g (h (f (g (h
-- x))))).
nubVars :: Expr -> [Expr]
-- | O(n^2). 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
-- ]
--
--
-- Runtime averages to O(n log n) on evenly distributed
-- expressions such as (f x + g y) + (h z + f w); and to
-- O(n^2) on deep expressions such as f (g (h (f (g (h
-- x))))).
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
-- | O(n). Like showPrecExpr but the precedence is taken from
-- the given operator name.
--
--
-- > showOpExpr "*" (two -*- three)
-- "(2 * 3)"
--
--
--
-- > showOpExpr "+" (two -*- three)
-- "2 * 3"
--
--
-- To imply that the surrounding environment is a function application,
-- use " " as the given operator.
--
--
-- > showOpExpr " " (two -*- three)
-- "(2 * 3)"
--
showOpExpr :: String -> Expr -> String
-- | O(n). Like showExpr but allows specifying the
-- surrounding precedence.
--
--
-- > showPrecExpr 6 (one -+- two)
-- "1 + 2"
--
--
--
-- > showPrecExpr 7 (one -+- two)
-- "(1 + 2)"
--
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 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. encompasses,
-- 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
-- | Given two Exprs, checks if the first expression encompasses the
-- second expression in terms of variables.
--
-- This is equivalent to flipping the arguments of isInstanceOf.
--
--
-- zero `encompasses` xx = False
-- xx `encompasses` zero = True
--
encompasses :: Expr -> Expr -> Bool
-- | This module is part of Express.
--
-- An experimental data structure for matching Exprs.
--
-- Warning (1): Take care when importing this module, the
-- interface is experimental and may change at every minor version.
--
-- Warning (2): YMMV: Do not expect this to be faster than
-- manually matching in a list, provisional experiments show that it can
-- be slower depending on the set of expressions being matched.
--
-- This module should be imported qualified as it exports definitions
-- called map, lookup, toList, fromList,
-- insert and empty:
--
--
-- import Data.Express.Triexpr (Triexpr)
-- import qualified Data.Express.Triexpr as T
--
module Data.Express.Triexpr
-- | A trie of Exprs.
--
-- In the representation, Nothing matches an App and Just
-- Expr an expression.
data Triexpr a
Triexpr :: [(Maybe Expr, Either (Triexpr a) (Expr, a))] -> Triexpr a
-- | An empty Triexpr.
empty :: Triexpr a
-- | Constructs a Triexpr encoding a single expression.
unit :: Expr -> a -> Triexpr a
-- | Merges two Triexprs.
merge :: Triexpr a -> Triexpr a -> Triexpr a
-- | Inserts an Expr into a Triexpr.
insert :: Expr -> a -> Triexpr a -> Triexpr a
-- | List all Expr stored in a Triexpr along with their
-- associated values.
toList :: Triexpr a -> [(Expr, a)]
-- | Constructs a Triexpr form a list of key Exprs and
-- associated values.
fromList :: [(Expr, a)] -> Triexpr a
-- | Maps a function to the stored values in a Triexpr.
map :: (a -> b) -> Triexpr a -> Triexpr b
-- | Performs a lookup in a Triexpr.
lookup :: Expr -> Triexpr a -> [(Expr, [(Expr, Expr)], a)]
instance GHC.Show.Show a => GHC.Show.Show (Data.Express.Triexpr.Triexpr a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Express.Triexpr.Triexpr a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Express.Triexpr.Triexpr a)
-- | 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). Returns whether an expression contains a hole
--
--
-- > hasHole $ hole (undefined :: Bool)
-- True
--
--
--
-- > hasHole $ value "not" not :$ val True
-- False
--
--
--
-- > hasHole $ value "not" not :$ hole (undefined :: Bool)
-- True
--
hasHole :: Expr -> Bool
-- | O(n). Returns whether an expression is complete. A complete
-- expression is one without holes.
--
--
-- > isComplete $ hole (undefined :: Bool)
-- False
--
--
--
-- > isComplete $ value "not" not :$ val True
-- True
--
--
--
-- > isComplete $ value "not" not :$ hole (undefined :: Bool)
-- False
--
--
-- isComplete is the negation of hasHole.
--
--
-- isComplete = not . hasHole
--
--
-- isComplete is to hasHole what isGround is to
-- hasVar.
isComplete :: 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^2). 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]
--
--
-- Runtime averages to O(n log n) on evenly distributed
-- expressions such as (f x + g y) + (h z + f w); and to
-- O(n^2) on deep expressions such as f (g (h (f (g (h
-- x))))).
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
-- | Fill holes in an expression with the given list.
--
--
-- > let i_ = hole (undefined :: Int)
-- > let e1 -+- e2 = value "+" ((+) :: Int -> Int -> Int) :$ e1 :$ e2
-- > let xx = var "x" (undefined :: Int)
-- > let yy = var "y" (undefined :: Int)
--
--
--
-- > fill (i_ -+- i_) [xx, yy]
-- x + y :: Int
--
--
--
-- > fill (i_ -+- i_) [xx, xx]
-- x + x :: Int
--
--
--
-- > let one = val (1::Int)
--
--
--
-- > fill (i_ -+- i_) [one, one -+- one]
-- 1 + (1 + 1) :: Int
--
--
-- This function silently remaining expressions:
--
--
-- > fill i_ [xx, yy]
-- x :: Int
--
--
-- This function silently keeps remaining holes:
--
--
-- > fill (i_ -+- i_ -+- i_) [xx, yy]
-- (x + y) + _ :: Int
--
--
-- This function silently skips remaining holes if one is not of the
-- right type:
--
--
-- > fill (i_ -+- i_ -+- i_) [xx, val 'c', yy]
-- (x + _) + _ :: Int
--
fill :: Expr -> [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, as it uses a
-- fake pair constructor.
--
--
-- > 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)
-- | O(1). Folds a trio/triple of Expr values into a single
-- Expr. (cf. unfoldTrio)
--
-- This always generates an ill-typed expression as it uses a fake
-- trio/triple constructor.
--
--
-- > foldTrio (val False, val (1::Int), val 'a')
-- (False,1,'a') :: ill-typed # ExprTrio $ Bool #
--
--
--
-- > foldTrio (val (0::Int), val True, val 'b')
-- (0,True,'b') :: ill-typed # ExprTrio $ 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)
-- > let zz = var "z" (undefined::Int)
-- > unfoldPair $ canonicalize $ foldPair (ii,kk,zz)
-- (x :: Int,y :: Int,z :: Int)
--
foldTrio :: (Expr, Expr, Expr) -> Expr
-- | O(1). Unfolds an Expr representing a trio/triple. This
-- reverses the effect of foldTrio.
--
--
-- > value ",," ((,,) :: Bool->Bool->Bool->(Bool,Bool,Bool)) :$ val True :$ val False :$ val True
-- (True,False,True) :: (Bool,Bool,Bool)
-- > unfoldTrio $ value ",," ((,,) :: Bool->Bool->Bool->(Bool,Bool,Bool)) :$ val True :$ val False :$ val True
-- (True :: Bool,False :: Bool,True :: Bool)
--
--
-- (cf. unfoldPair)
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 (Show a, 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, 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)
instance Data.Express.Express.Express GHC.Types.Double
instance Data.Express.Express.Express GHC.Types.Float
instance Data.Express.Express.Express GHC.Int.Int8
instance Data.Express.Express.Express GHC.Int.Int16
instance Data.Express.Express.Express GHC.Int.Int32
instance Data.Express.Express.Express GHC.Int.Int64
instance Data.Express.Express.Express GHC.Types.Word
instance Data.Express.Express.Express GHC.Word.Word8
instance Data.Express.Express.Express GHC.Word.Word16
instance Data.Express.Express.Express GHC.Word.Word32
instance Data.Express.Express.Express GHC.Word.Word64
instance Data.Express.Express.Express GHC.Unicode.GeneralCategory
-- | 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:
--
--
--
-- If you're a Express user, you're probably better of importing
-- Data.Express.
module Data.Express.Basic
-- | 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
-- | O(n+m). Returns an equation between two expressions given that
-- it is possible to do so from == operators given in the argument
-- instances list.
--
-- When not possible, this function returns False encoded as an
-- Expr.
mkEquation :: [Expr] -> Expr -> Expr -> Expr
-- | O(n+m). Returns a less-than-or-equal-to inequation between two
-- expressions given that it is possible to do so from <=
-- operators given in the argument instances list.
--
-- When not possible, this function returns False encoded as an
-- Expr.
mkComparisonLE :: [Expr] -> Expr -> Expr -> Expr
-- | O(n+m). Returns a less-than inequation between two expressions
-- given that it is possible to do so from < operators given in
-- the argument instances list.
--
-- When not possible, this function returns False encoded as an
-- Expr.
mkComparisonLT :: [Expr] -> Expr -> Expr -> Expr
-- | O(n+m). Like mkEquation, mkComparisonLE and
-- mkComparisonLT but allows providing the binary operator name.
--
-- When not possible, this function returns False encoded as an
-- Expr.
mkComparison :: String -> [Expr] -> Expr -> Expr -> Expr
-- | O(n). Lookups for a comparison function (:: a -> a ->
-- Bool) with the given name and argument type.
lookupComparison :: String -> TypeRep -> [Expr] -> Maybe Expr
-- | O(n+m). Like lookupNames but returns a list of variables
-- encoded as Exprs.
listVarsWith :: [Expr] -> Expr -> [Expr]
-- | O(n+m). Like name but lifted over an instance list and
-- an Expr.
--
--
-- > lookupName preludeNameInstances (val False)
-- "p"
--
--
--
-- > lookupName preludeNameInstances (val (0::Int))
-- "x"
--
--
-- This function defaults to "x" when no appropriate name
-- is found.
--
--
-- > lookupName [] (val False)
-- "x"
--
lookupName :: [Expr] -> Expr -> String
-- | O(n+m). A mix between lookupName and names: this
-- returns an infinite list of names based on an instances list and an
-- Expr.
lookupNames :: [Expr] -> Expr -> [String]
-- | Given a list of functional expressions and another expression, returns
-- a list of valid applications.
validApps :: [Expr] -> Expr -> [Expr]
-- | Like validApps but returns a Maybe value.
findValidApp :: [Expr] -> Expr -> Maybe Expr
-- | A list of reified Name instances for an arbitrary selection of
-- types from the Haskell Prelude.
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]
--
--
-- When applying this to expressions already containing variables clashes
-- are avoided and these variables are not touched:
--
--
-- > canonicalVariations $ i_ -+- ii -+- jj -+- i_
-- [ x + i + j + y :: Int
-- , x + i + j + y :: Int ]
--
--
--
-- > canonicalVariations $ ii -+- jj
-- [i + j :: Int]
--
--
--
-- > canonicalVariations $ xx -+- i_ -+- i_ -+- length' (c_ -:- unit c_) -+- yy
-- [ (((x + z) + x') + length (c:d:"")) + y :: Int
-- , (((x + z) + x') + length (c:c:"")) + y :: Int
-- , (((x + z) + z) + length (c:d:"")) + y :: Int
-- , (((x + z) + z) + length (c:c:"")) + y :: Int
-- ]
--
canonicalVariations :: Expr -> [Expr]
-- | Returns the most general canonical variation of an Expr by
-- filling holes with variables.
--
--
-- > mostGeneralCanonicalVariation $ i_
-- x :: Int
--
--
--
-- > mostGeneralCanonicalVariation $ i_ -+- i_
-- x + y :: Int
--
--
--
-- > mostGeneralCanonicalVariation $ i_ -+- i_ -+- i_
-- (x + y) + z :: Int
--
--
--
-- > mostGeneralCanonicalVariation $ i_ -+- ord' c_
-- x + ord c :: Int
--
--
--
-- > mostGeneralCanonicalVariation $ i_ -+- i_ -+- ord' c_
-- (x + y) + ord c :: Int
--
--
--
-- > mostGeneralCanonicalVariation $ i_ -+- i_ -+- length' (c_ -:- unit c_)
-- (x + y) + length (c:d:"") :: Int
--
--
-- In an expression without holes this functions just returns the given
-- expression itself:
--
--
-- > mostGeneralCanonicalVariation $ val (0 :: Int)
-- 0 :: Int
--
--
--
-- > mostGeneralCanonicalVariation $ ord' bee
-- ord 'b' :: Int
--
--
-- This function is the same as taking the head of
-- canonicalVariations but a bit faster.
mostGeneralCanonicalVariation :: Expr -> Expr
-- | Returns the most specific canonical variation of an Expr by
-- filling holes with variables.
--
--
-- > mostSpecificCanonicalVariation $ i_
-- x :: Int
--
--
--
-- > mostSpecificCanonicalVariation $ i_ -+- i_
-- x + x :: Int
--
--
--
-- > mostSpecificCanonicalVariation $ i_ -+- i_ -+- i_
-- (x + x) + x :: Int
--
--
--
-- > mostSpecificCanonicalVariation $ i_ -+- ord' c_
-- x + ord c :: Int
--
--
--
-- > mostSpecificCanonicalVariation $ i_ -+- i_ -+- ord' c_
-- (x + x) + ord c :: Int
--
--
--
-- > mostSpecificCanonicalVariation $ i_ -+- i_ -+- length' (c_ -:- unit c_)
-- (x + x) + length (c:c:"") :: Int
--
--
-- In an expression without holes this functions just returns the given
-- expression itself:
--
--
-- > mostSpecificCanonicalVariation $ val (0 :: Int)
-- 0 :: Int
--
--
--
-- > mostSpecificCanonicalVariation $ ord' bee
-- ord 'b' :: Int
--
--
-- This function is the same as taking the last of
-- canonicalVariations but a bit faster.
mostSpecificCanonicalVariation :: 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]
-- | A faster version of mostGeneralCanonicalVariation that
-- disregards name clashes across different types. Consider using
-- mostGeneralCanonicalVariation instead.
--
-- The same caveats of fastCanonicalVariations do apply here.
fastMostGeneralVariation :: Expr -> Expr
-- | A faster version of mostSpecificCanonicalVariation that
-- disregards name clashes across different types. Consider using
-- mostSpecificCanonicalVariation instead.
--
-- The same caveats of fastCanonicalVariations do apply here.
fastMostSpecificVariation :: 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 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"
--
--
-- 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 with
-- $$.
--
--
-- > 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 :: 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 :: 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). Returns whether the given Expr is of a functional
-- type. This is the same as checking if the arity of the given
-- Expr is non-zero.
--
--
-- > isFun (value "abs" (abs :: Int -> Int))
-- True
--
--
--
-- > isFun (val (1::Int))
-- False
--
--
--
-- > isFun (value "const" (const :: Bool -> Bool -> Bool) :$ val False)
-- True
--
isFun :: 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 an expression contains a hole
--
--
-- > hasHole $ hole (undefined :: Bool)
-- True
--
--
--
-- > hasHole $ value "not" not :$ val True
-- False
--
--
--
-- > hasHole $ value "not" not :$ hole (undefined :: Bool)
-- True
--
hasHole :: 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). Returns whether an expression is complete. A complete
-- expression is one without holes.
--
--
-- > isComplete $ hole (undefined :: Bool)
-- False
--
--
--
-- > isComplete $ value "not" not :$ val True
-- True
--
--
--
-- > isComplete $ value "not" not :$ hole (undefined :: Bool)
-- False
--
--
-- isComplete is the negation of hasHole.
--
--
-- isComplete = not . hasHole
--
--
-- isComplete is to hasHole what isGround is to
-- hasVar.
isComplete :: 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
--
--
-- This comparison is not a total order.
compareComplexity :: Expr -> Expr -> Ordering
-- | O(n). Lexicographical structural comparison of Exprs
-- where variables < constants < applications then types are
-- compared before string representations.
--
--
-- > compareLexicographically one (one -+- one)
-- LT
-- > compareLexicographically one zero
-- GT
-- > compareLexicographically (xx -+- zero) (zero -+- xx)
-- LT
-- > compareLexicographically (zero -+- xx) (zero -+- xx)
-- EQ
--
--
-- (cf. compareTy)
--
-- This comparison is a total order.
compareLexicographically :: Expr -> Expr -> Ordering
-- | O(n). A fast total order between Exprs that can be used
-- when sorting Expr values.
--
-- This is lazier than its counterparts compareComplexity and
-- compareLexicographically and tries to evaluate the given
-- Exprs as least as possible.
compareQuickly :: 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). 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
-- | O(n). Like showExpr but allows specifying the
-- surrounding precedence.
--
--
-- > showPrecExpr 6 (one -+- two)
-- "1 + 2"
--
--
--
-- > showPrecExpr 7 (one -+- two)
-- "(1 + 2)"
--
showPrecExpr :: Int -> Expr -> String
-- | O(n). Like showPrecExpr but the precedence is taken from
-- the given operator name.
--
--
-- > showOpExpr "*" (two -*- three)
-- "(2 * 3)"
--
--
--
-- > showOpExpr "+" (two -*- three)
-- "2 * 3"
--
--
-- To imply that the surrounding environment is a function application,
-- use " " as the given operator.
--
--
-- > showOpExpr " " (two -*- three)
-- "(2 * 3)"
--
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
-- ]
--
consts :: Expr -> [Expr]
-- | O(n^3) 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
-- ]
--
--
-- Runtime averages to O(n^2 log n) on evenly distributed
-- expressions such as (f x + g y) + (h z + f w); and to
-- O(n^3) on deep expressions such as f (g (h (f (g (h
-- x))))).
nubSubexprs :: Expr -> [Expr]
-- | O(n^2). 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
-- ]
--
--
-- Runtime averages to O(n log n) on evenly distributed
-- expressions such as (f x + g y) + (h z + f w); and to
-- O(n^2) on deep expressions such as f (g (h (f (g (h
-- x))))).
nubValues :: Expr -> [Expr]
-- | O(n^2). 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]
--
--
-- Runtime averages to O(n log n) on evenly distributed
-- expressions such as (f x + g y) + (h z + f w); and to
-- O(n^2) on deep expressions such as f (g (h (f (g (h
-- x))))).
nubVars :: Expr -> [Expr]
-- | O(n^2). 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
-- ]
--
--
-- Runtime averages to O(n log n) on evenly distributed
-- expressions such as (f x + g y) + (h z + f w); and to
-- O(n^2) on deep expressions such as f (g (h (f (g (h
-- x))))).
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
--
--
-- 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
-- | 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^2). 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]
--
--
-- Runtime averages to O(n log n) on evenly distributed
-- expressions such as (f x + g y) + (h z + f w); and to
-- O(n^2) on deep expressions such as f (g (h (f (g (h
-- x))))).
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
-- | Fill holes in an expression with the given list.
--
--
-- > let i_ = hole (undefined :: Int)
-- > let e1 -+- e2 = value "+" ((+) :: Int -> Int -> Int) :$ e1 :$ e2
-- > let xx = var "x" (undefined :: Int)
-- > let yy = var "y" (undefined :: Int)
--
--
--
-- > fill (i_ -+- i_) [xx, yy]
-- x + y :: Int
--
--
--
-- > fill (i_ -+- i_) [xx, xx]
-- x + x :: Int
--
--
--
-- > let one = val (1::Int)
--
--
--
-- > fill (i_ -+- i_) [one, one -+- one]
-- 1 + (1 + 1) :: Int
--
--
-- This function silently remaining expressions:
--
--
-- > fill i_ [xx, yy]
-- x :: Int
--
--
-- This function silently keeps remaining holes:
--
--
-- > fill (i_ -+- i_ -+- i_) [xx, yy]
-- (x + y) + _ :: Int
--
--
-- This function silently skips remaining holes if one is not of the
-- right type:
--
--
-- > fill (i_ -+- i_ -+- i_) [xx, val 'c', yy]
-- (x + _) + _ :: Int
--
fill :: Expr -> [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, as it uses a
-- fake pair constructor.
--
--
-- > 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)
-- | O(1). Folds a trio/triple of Expr values into a single
-- Expr. (cf. unfoldTrio)
--
-- This always generates an ill-typed expression as it uses a fake
-- trio/triple constructor.
--
--
-- > foldTrio (val False, val (1::Int), val 'a')
-- (False,1,'a') :: ill-typed # ExprTrio $ Bool #
--
--
--
-- > foldTrio (val (0::Int), val True, val 'b')
-- (0,True,'b') :: ill-typed # ExprTrio $ 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)
-- > let zz = var "z" (undefined::Int)
-- > unfoldPair $ canonicalize $ foldPair (ii,kk,zz)
-- (x :: Int,y :: Int,z :: Int)
--
foldTrio :: (Expr, Expr, Expr) -> Expr
-- | O(1). Unfolds an Expr representing a trio/triple. This
-- reverses the effect of foldTrio.
--
--
-- > value ",," ((,,) :: Bool->Bool->Bool->(Bool,Bool,Bool)) :$ val True :$ val False :$ val True
-- (True,False,True) :: (Bool,Bool,Bool)
-- > unfoldTrio $ value ",," ((,,) :: Bool->Bool->Bool->(Bool,Bool,Bool)) :$ val True :$ val False :$ val True
-- (True :: Bool,False :: Bool,True :: Bool)
--
--
-- (cf. unfoldPair)
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]
-- | 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]
--
--
-- When applying this to expressions already containing variables clashes
-- are avoided and these variables are not touched:
--
--
-- > canonicalVariations $ i_ -+- ii -+- jj -+- i_
-- [ x + i + j + y :: Int
-- , x + i + j + y :: Int ]
--
--
--
-- > canonicalVariations $ ii -+- jj
-- [i + j :: Int]
--
--
--
-- > canonicalVariations $ xx -+- i_ -+- i_ -+- length' (c_ -:- unit c_) -+- yy
-- [ (((x + z) + x') + length (c:d:"")) + y :: Int
-- , (((x + z) + x') + length (c:c:"")) + y :: Int
-- , (((x + z) + z) + length (c:d:"")) + y :: Int
-- , (((x + z) + z) + length (c:c:"")) + y :: Int
-- ]
--
canonicalVariations :: Expr -> [Expr]
-- | Returns the most general canonical variation of an Expr by
-- filling holes with variables.
--
--
-- > mostGeneralCanonicalVariation $ i_
-- x :: Int
--
--
--
-- > mostGeneralCanonicalVariation $ i_ -+- i_
-- x + y :: Int
--
--
--
-- > mostGeneralCanonicalVariation $ i_ -+- i_ -+- i_
-- (x + y) + z :: Int
--
--
--
-- > mostGeneralCanonicalVariation $ i_ -+- ord' c_
-- x + ord c :: Int
--
--
--
-- > mostGeneralCanonicalVariation $ i_ -+- i_ -+- ord' c_
-- (x + y) + ord c :: Int
--
--
--
-- > mostGeneralCanonicalVariation $ i_ -+- i_ -+- length' (c_ -:- unit c_)
-- (x + y) + length (c:d:"") :: Int
--
--
-- In an expression without holes this functions just returns the given
-- expression itself:
--
--
-- > mostGeneralCanonicalVariation $ val (0 :: Int)
-- 0 :: Int
--
--
--
-- > mostGeneralCanonicalVariation $ ord' bee
-- ord 'b' :: Int
--
--
-- This function is the same as taking the head of
-- canonicalVariations but a bit faster.
mostGeneralCanonicalVariation :: Expr -> Expr
-- | Returns the most specific canonical variation of an Expr by
-- filling holes with variables.
--
--
-- > mostSpecificCanonicalVariation $ i_
-- x :: Int
--
--
--
-- > mostSpecificCanonicalVariation $ i_ -+- i_
-- x + x :: Int
--
--
--
-- > mostSpecificCanonicalVariation $ i_ -+- i_ -+- i_
-- (x + x) + x :: Int
--
--
--
-- > mostSpecificCanonicalVariation $ i_ -+- ord' c_
-- x + ord c :: Int
--
--
--
-- > mostSpecificCanonicalVariation $ i_ -+- i_ -+- ord' c_
-- (x + x) + ord c :: Int
--
--
--
-- > mostSpecificCanonicalVariation $ i_ -+- i_ -+- length' (c_ -:- unit c_)
-- (x + x) + length (c:c:"") :: Int
--
--
-- In an expression without holes this functions just returns the given
-- expression itself:
--
--
-- > mostSpecificCanonicalVariation $ val (0 :: Int)
-- 0 :: Int
--
--
--
-- > mostSpecificCanonicalVariation $ ord' bee
-- ord 'b' :: Int
--
--
-- This function is the same as taking the last of
-- canonicalVariations but a bit faster.
mostSpecificCanonicalVariation :: 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]
-- | A faster version of mostGeneralCanonicalVariation that
-- disregards name clashes across different types. Consider using
-- mostGeneralCanonicalVariation instead.
--
-- The same caveats of fastCanonicalVariations do apply here.
fastMostGeneralVariation :: Expr -> Expr
-- | A faster version of mostSpecificCanonicalVariation that
-- disregards name clashes across different types. Consider using
-- mostSpecificCanonicalVariation instead.
--
-- The same caveats of fastCanonicalVariations do apply here.
fastMostSpecificVariation :: Expr -> Expr
-- | 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. encompasses,
-- 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
-- | Given two Exprs, checks if the first expression encompasses the
-- second expression in terms of variables.
--
-- This is equivalent to flipping the arguments of isInstanceOf.
--
--
-- zero `encompasses` xx = False
-- xx `encompasses` zero = True
--
encompasses :: 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.
--
--
-- 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 (Show a, 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 ]
--
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
-- | O(n+m). Returns an equation between two expressions given that
-- it is possible to do so from == operators given in the argument
-- instances list.
--
-- When not possible, this function returns False encoded as an
-- Expr.
mkEquation :: [Expr] -> Expr -> Expr -> Expr
-- | O(n+m). Returns a less-than-or-equal-to inequation between two
-- expressions given that it is possible to do so from <=
-- operators given in the argument instances list.
--
-- When not possible, this function returns False encoded as an
-- Expr.
mkComparisonLE :: [Expr] -> Expr -> Expr -> Expr
-- | O(n+m). Returns a less-than inequation between two expressions
-- given that it is possible to do so from < operators given in
-- the argument instances list.
--
-- When not possible, this function returns False encoded as an
-- Expr.
mkComparisonLT :: [Expr] -> Expr -> Expr -> Expr
-- | O(n+m). Like mkEquation, mkComparisonLE and
-- mkComparisonLT but allows providing the binary operator name.
--
-- When not possible, this function returns False encoded as an
-- Expr.
mkComparison :: String -> [Expr] -> Expr -> Expr -> Expr
-- | O(n). Lookups for a comparison function (:: a -> a ->
-- Bool) with the given name and argument type.
lookupComparison :: String -> TypeRep -> [Expr] -> Maybe Expr
-- | O(n+m). Like lookupNames but returns a list of variables
-- encoded as Exprs.
listVarsWith :: [Expr] -> Expr -> [Expr]
-- | O(n+m). Like name but lifted over an instance list and
-- an Expr.
--
--
-- > lookupName preludeNameInstances (val False)
-- "p"
--
--
--
-- > lookupName preludeNameInstances (val (0::Int))
-- "x"
--
--
-- This function defaults to "x" when no appropriate name
-- is found.
--
--
-- > lookupName [] (val False)
-- "x"
--
lookupName :: [Expr] -> Expr -> String
-- | O(n+m). A mix between lookupName and names: this
-- returns an infinite list of names based on an instances list and an
-- Expr.
lookupNames :: [Expr] -> Expr -> [String]
-- | Given a list of functional expressions and another expression, returns
-- a list of valid applications.
validApps :: [Expr] -> Expr -> [Expr]
-- | Like validApps but returns a Maybe value.
findValidApp :: [Expr] -> Expr -> Maybe Expr
-- | A list of reified Name instances for an arbitrary selection of
-- types from the Haskell Prelude.
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
-- polymorphic 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
-- | The ==> operator encoded as an 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
infixr 2 -||-
-- | The function && lifted over the Expr type.
--
--
-- > pp -&&- qq
-- p && q :: Bool
--
--
--
-- > false -&&- true
-- False && True :: Bool
--
--
--
-- > evalBool $ false -&&- true
-- False
--
(-&&-) :: Expr -> Expr -> Expr
infixr 3 -&&-
-- | The function ==> lifted over Exprs.
--
--
-- > false -==>- true
-- False ==> True :: Bool
--
--
--
-- > evl $ false -==>- true :: Bool
-- True
--
(-==>-) :: Expr -> Expr -> Expr
infixr 0 -==>-
-- | Constructs an equation between two Exprs.
--
--
-- > xx -==- zero
-- x == 0 :: Bool
--
--
--
-- > cc -==- dee
-- c == 'd' :: Bool
--
--
-- This works for the Int, Bool, Char argument types
-- and their lists.
(-==-) :: Expr -> Expr -> Expr
infix 4 -==-
-- | Constructs an inequation between two Exprs.
--
--
-- > xx -/=- zero
-- x /= 0 :: Bool
--
--
--
-- > cc -/=- ae
-- c /= 'a' :: Bool
--
(-/=-) :: Expr -> Expr -> Expr
infix 4 -/=-
-- | Constructs a less-than-or-equal inequation between two Exprs.
--
--
-- > xx -<=- zero
-- x <= 0 :: Bool
--
--
--
-- > cc -<=- ae
-- c <= 'a' :: Bool
--
(-<=-) :: Expr -> Expr -> Expr
infix 4 -<=-
-- | Constructs a less-than inequation between two Exprs.
--
--
-- > xx -<- zero
-- x < 0 :: Bool
--
--
--
-- > cc -<- bee
-- c < 'b' :: Bool
--
(-<-) :: Expr -> Expr -> Expr
infix 4 -<-
-- | Constructs an Expr-encoded compare operation between two
-- Exprs.
--
--
-- > xx `compare'` zero
-- compare x 0 :: Ordering
--
--
--
-- > compare' ae bee
-- compare 'a' 'b' :: Ordering
--
compare' :: Expr -> Expr -> Expr
-- | A virtual function if :: Bool -> a -> a -> a lifted
-- over the Expr type. This is displayed as an if-then-else.
--
--
-- > if' pp zero xx
-- (if p then 0 else x) :: Int
--
--
--
-- > zz -*- if' pp xx yy
-- z * (if p then x else y) :: Int
--
--
--
-- > if' pp false true -||- if' qq true false
-- (if p then False else True) || (if q then True else False) :: Bool
--
--
--
-- > evl $ if' true (val 't') (val 'f') :: Char
-- 't'
--
if' :: Expr -> 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
-- | A variable i of Int type.
--
--
-- > ii
-- i :: Int
--
ii :: Expr
-- | A variable j of Int type.
--
--
-- > jj
-- j :: Int
--
jj :: Expr
-- | A variable k of Int type.
--
--
-- > kk
-- k :: Int
--
kk :: Expr
-- | A variable i' of Int type.
--
--
-- > ii'
-- i' :: Int
--
ii' :: Expr
-- | A variable l of Int type.
--
--
-- > ll
-- l :: Int
--
ll :: Expr
-- | A variable m of Int type.
--
--
-- > mm
-- m :: Int
--
mm :: Expr
-- | A variable n of Int type.
--
--
-- > nn
-- n :: Int
--
nn :: 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 4 bound to the Int type encoded as an
-- Expr.
--
--
-- > four
-- 4 :: Int
--
four :: Expr
-- | The value 5 bound to the Int type encoded as an
-- Expr.
--
--
-- > five
-- 5 :: Int
--
five :: Expr
-- | The value 6 bound to the Int type encoded as an
-- Expr.
--
--
-- > six
-- 6 :: Int
--
six :: Expr
-- | The value 7 bound to the Int type encoded as an
-- Expr.
--
--
-- > seven
-- 7 :: Int
--
seven :: Expr
-- | The value 8 bound to the Int type encoded as an
-- Expr.
--
--
-- > eight
-- 8 :: Int
--
eight :: Expr
-- | The value 9 bound to the Int type encoded as an
-- Expr.
--
--
-- > nine
-- 9 :: Int
--
nine :: Expr
-- | The value 10 bound to the Int type encoded as an
-- Expr.
--
--
-- > ten
-- 10 :: Int
--
ten :: Expr
-- | The value 11 bound to the Int type encoded as an
-- Expr.
--
--
-- > eleven
-- 11 :: Int
--
eleven :: Expr
-- | The value 12 bound to the Int type encoded as an
-- Expr.
--
--
-- > twelve
-- 12 :: Int
--
twelve :: 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
-- | signum over the Int type encoded as an Expr.
--
--
-- > signumE
-- signum :: Int -> Int
--
signumE :: 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
-- | The const function lifted over the Expr type.
--
--
-- > const' zero one
-- const 0 1 :: Int
--
--
-- This works for the argument types Int, Char, Bool
-- and their lists.
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
-- | signum over the Int type lifted over the Expr
-- type.
--
--
-- > signum' xx'
-- signum x' :: Int
--
--
--
-- > evl (signum' minusTwo) :: Int
-- -1
--
signum' :: 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 subtraction - operator encoded as an Expr.
--
--
-- > minus :$ one
-- (1 -) :: Int -> Int
--
--
--
-- > minus :$ one :$ zero
-- 1 - 0 :: Int
--
minus :: 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
infixl 7 -*-
-- | 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 function h of 'Int -> Int' type lifted over the
-- Expr type.
--
--
-- > hh zz
-- h z :: Int
--
hh :: Expr -> Expr
-- | A variable h of 'Int -> Int' type encoded as an
-- Expr.
--
--
-- > hhE
-- h :: Int -> Int
--
hhE :: 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
-- | $ lifted over Exprs
--
--
-- > absE -$- one
-- abs $ 1 :: Int
--
--
-- Works for Int, Bool, Char argument types and
-- their lists.
(-$-) :: Expr -> Expr -> Expr
infixl 6 -$-
-- | odd with an Int argument lifted over the Expr
-- type.
--
--
-- > odd' (xx -+- one)
-- odd (x + 1) :: Bool
--
--
--
-- > evl (odd' two) :: Bool
-- False
--
odd' :: Expr -> Expr
-- | even with an Int argument lifted over the Expr
-- type.
--
--
-- > even' (xx -+- two)
-- even (x + 2) :: Bool
--
--
--
-- > evl (even' two) :: Bool
-- True
--
even' :: Expr -> Expr
-- | A hole of Char type encoded as an Expr.
--
--
-- > c_
-- _ :: Char
--
c_ :: Expr
-- | A hole of String type encoded as an Expr.
--
--
-- > cs_
-- _ :: [Char]
--
cs_ :: Expr
-- | A variable named c of type Char encoded as an
-- Expr.
--
--
-- > cc
-- c :: Char
--
cc :: Expr
-- | A variable named c of type Char encoded as an
-- Expr.
--
--
-- > dd
-- d :: Char
--
dd :: Expr
-- | A variable named cs of type String encoded as an
-- Expr.
--
--
-- > ccs
-- cs :: [Char]
--
ccs :: Expr
-- | The character 'a' encoded as an Expr.
--
--
-- > ae
-- 'a' :: Char
--
--
--
-- > evl ae :: Char
-- 'a'
--
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
-- | The character 'z' encoded as an Expr
--
--
-- > zed
-- 'z' :: Char
--
--
--
-- > evl zed :: Char
-- 'z'
--
--
-- (cf. zee)
zed :: Expr
-- | The character 'z' encoded as an Expr
--
--
-- > zee
-- 'z' :: Char
--
--
--
-- > evl zee :: Char
-- 'z'
--
--
-- (cf. zed)
zee :: Expr
-- | The space character encoded as an Expr
--
--
-- > space
-- ' ' :: Char
--
space :: Expr
-- | The line break character encoded as an Expr
--
--
-- > lineBreak
-- '\n' :: Char
--
lineBreak :: Expr
-- | The ord function lifted over Expr
--
--
-- > ord' bee
-- ord 'b' :: Int
--
--
--
-- > evl (ord' bee)
-- 98
--
ord' :: Expr -> Expr
-- | The ord function encoded as an 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
-- | A variable named zs of type [Int] encoded as an
-- Expr.
--
--
-- > yys
-- ys :: [Int]
--
zzs :: 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 null lifted over the Expr type. Works for the
-- element types Int, Char and Bool.
--
--
-- > null' $ unit one
-- null [1] :: Bool
--
--
--
-- > null' $ nil
-- null [] :: Bool
--
--
--
-- > evl $ null' nil :: Bool
-- True
--
null' :: 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
-- | List elem lifted over the Expr type. Works for the
-- element types Int, Char and Bool.
--
--
-- > elem' false (false -:- unit true)
-- elem False [False,True] :: Bool
--
--
--
-- > evl $ elem' false (false -:- unit true) :: Bool
-- True
--
elem' :: Expr -> Expr -> Expr
-- | List sort lifted over the Expr type. Works for the
-- element types Int, Char and Bool.
--
--
-- > sort' $ unit one
-- sort [1] :: Int
--
--
--
-- > sort' $ unit bee
-- sort "b" :: Int
--
--
--
-- > sort' $ zero -:- unit two
-- sort [0,2] :: Int
--
--
--
-- > evl $ sort' $ two -:- unit one :: [Int]
-- [1,2]
--
sort' :: Expr -> Expr
-- | List insert lifted over the Expr type. Works for the
-- element types Int, Char and Bool.
--
--
-- > insert' zero nilInt
-- insert 0 [] :: [Int]
--
--
--
-- > insert' false (false -:- unit true)
-- insert False [False,True] :: [Bool]
--
insert' :: Expr -> Expr -> Expr
-- | A typed hole of [Bool] type encoded as an Expr.
--
--
-- > bs_
-- _ :: [Bool]
--
bs_ :: Expr
-- | Expr representing a variable p' :: `[Bool]`.
--
--
-- > pps
-- ps :: [Bool]
--
pps :: Expr
-- | A typed hole of '[Bool]' type
--
--
-- > qqs
-- qs :: [Bool]
--
qqs :: Expr
-- | and lifted over the Expr type.
--
--
-- > and' pps
-- and ps :: Bool
--
--
--
-- > evl (and' $ expr [False,True]) :: Bool
-- False
--
and' :: Expr -> Expr
-- | or lifted over the Expr type.
--
--
-- > or' pps
-- or ps :: Bool
--
--
--
-- > evl (or' $ expr [False,True]) :: Bool
-- True
--
or' :: Expr -> Expr
-- | sum of Int elements lifted over the Expr type.
--
--
-- > sum' xxs
-- sum xs :: Int
--
--
--
-- > evl (sum' $ expr [1,2,3::Int]) :: Int
-- 6
--
sum' :: Expr -> Expr
-- | product of Int elements lifted over the Expr
-- type.
--
--
-- > product' xxs
-- product xs :: Int
--
--
--
-- > evl (product' $ expr [1,2,3::Int]) :: Int
-- 6
--
product' :: Expr -> Expr
-- | Append for list of Ints encoded as an Expr.
appendInt :: Expr
-- | Nothing bound to the Maybe Int type encoded as an
-- Expr.
--
-- This is an alias to nothingInt.
nothing :: Expr
-- | Nothing bound to the Maybe Int type encoded as an
-- Expr.
nothingInt :: Expr
-- | Nothing bound to the Maybe Bool type encoded as
-- an Expr.
nothingBool :: Expr
-- | The Just constructor lifted over the Expr type.
--
-- This works for the Bool and Int argument types.
--
--
-- > just zero
-- Just 0 :: Maybe Int
-- > just false
-- Just False :: Maybe Bool
--
just :: Expr -> Expr
-- | The Just constructor of the Int element type encoded as
-- an Expr.
justInt :: Expr
-- | The Just constructor of the Bool element type encoded as
-- an Expr.
justBool :: Expr
-- | The pair constructor ( :: ... -> (Int,Int) ) encoded as an
-- Expr.
comma :: Expr
-- | The pair constructor lifted over Exprs.
--
-- This works for the Int and Bool element types by
-- differently from foldPair by returning a well-typed expression.
pair :: Expr -> Expr -> Expr
-- | An infix synonym of pair.
(-|-) :: Expr -> Expr -> Expr
-- | The triple/trio constructor lifted over Exprs.
--
-- This only works for the Int element type.
triple :: Expr -> Expr -> Expr -> Expr
-- | The quadruple constructor lifted over Exprs.
--
-- This only works for the Int element type.
quadruple :: Expr -> Expr -> Expr -> Expr -> Expr
-- | The quintuple constructor lifted over Exprs.
--
-- This only works for the Int element type.
quintuple :: Expr -> Expr -> Expr -> Expr -> Expr -> Expr
-- | The sixtuple constructor lifted over Exprs.
--
-- This only works for the Int element type.
sixtuple :: Expr -> Expr -> Expr -> Expr -> Expr -> Expr -> Expr
-- | Function composition encoded as an Expr:
--
--
-- > compose
-- (.) :: (Int -> Int) -> (Int -> Int) -> Int -> Int
--
compose :: Expr
-- | map over the Int element type encoded as an Expr
--
--
-- > mapE
-- map :: (Int -> Int) -> [Int] -> [Int]
--
mapE :: Expr
-- | Function composition . lifted over Expr.
--
--
-- > absE -.- negateE
-- abs . negate :: Int -> Int
--
--
--
-- > absE -.- negateE :$ one
-- (abs . negate) 1 :: Int
--
--
-- This works for Int, Bool, Char and their lists.
(-.-) :: Expr -> Expr -> Expr
-- | map lifted over Exprs.
--
--
-- > map' absE (unit one)
-- map abs [1] :: [Int]
--
map' :: Expr -> Expr -> Expr
-- | enumFrom lifted over Exprs.
--
--
-- > enumFrom' zero
-- enumFrom 0 :: [Int]
--
--
-- Works for Ints, Bools and Chars.
enumFrom' :: Expr -> Expr
-- | enumFrom lifted over Exprs named as ".." for
-- pretty-printing.
--
--
-- > (-..) one
-- [1..] :: [Int]
--
--
-- Works for Ints, Bools and Chars.
(-..) :: Expr -> Expr
-- | enumFromTo lifted over Exprs
--
--
-- > enumFromTo' zero four
-- enumFromTo 0 4 :: [Int]
--
enumFromTo' :: Expr -> Expr -> Expr
-- | enumFromTo lifted over Exprs but named as ".."
-- for pretty-printing.
--
--
-- > zero -..- four
-- [0..4] :: [Int]
--
(-..-) :: Expr -> Expr -> Expr
-- | enumFromThen lifted over Exprs
--
--
-- > enumFromThen' zero ten
-- enumFromThen 0 10 :: [Int]
--
enumFromThen' :: Expr -> Expr -> Expr
-- | enumFromThen lifted over Exprs but named as
-- ",.." for pretty printing.
--
--
-- > zero -... ten
-- [0,10..] :: [Int]
--
(-...) :: Expr -> Expr -> Expr
-- | enumFromThenTo lifted over Exprs.
--
--
-- > enumFromThenTo' zero two ten
-- enumFromThenTo 0 2 10 :: [Int]
--
enumFromThenTo' :: Expr -> Expr -> Expr -> Expr
-- | enumFromThenTo lifted over Exprs but named as
-- ",.." for pretty-printing.
--
--
-- > (zero -...- two) ten
-- [0,2..10] :: [Int]
--
(-...-) :: Expr -> Expr -> Expr -> Expr