Copyright | (c) 2019-2021 Rudy Matela |
---|---|
License | 3-Clause BSD (see the file LICENSE) |
Maintainer | Rudy Matela <rudy@matela.com.br> |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
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 Expr
s.
Synopsis
- data Expr
- value :: Typeable a => String -> a -> Expr
- val :: (Typeable a, Show a) => a -> Expr
- ($$) :: Expr -> Expr -> Maybe Expr
- var :: Typeable a => String -> a -> Expr
- evaluate :: Typeable a => Expr -> Maybe a
- eval :: Typeable a => a -> Expr -> a
- evl :: Typeable a => Expr -> a
- typ :: Expr -> TypeRep
- etyp :: Expr -> Either (TypeRep, TypeRep) TypeRep
- mtyp :: Expr -> Maybe TypeRep
- toDynamic :: Expr -> Maybe Dynamic
- isValue :: Expr -> Bool
- isApp :: Expr -> Bool
- isVar :: Expr -> Bool
- isConst :: Expr -> Bool
- isIllTyped :: Expr -> Bool
- isWellTyped :: Expr -> Bool
- isFun :: Expr -> Bool
- hasVar :: Expr -> Bool
- isGround :: Expr -> Bool
- compareComplexity :: Expr -> Expr -> Ordering
- arity :: Expr -> Int
- size :: Expr -> Int
- depth :: Expr -> Int
- height :: Expr -> Int
- subexprs :: Expr -> [Expr]
- values :: Expr -> [Expr]
- vars :: Expr -> [Expr]
- consts :: Expr -> [Expr]
- nubSubexprs :: Expr -> [Expr]
- nubValues :: Expr -> [Expr]
- nubVars :: Expr -> [Expr]
- nubConsts :: Expr -> [Expr]
- unfoldApp :: Expr -> [Expr]
- showExpr :: Expr -> String
- showOpExpr :: String -> Expr -> String
- showPrecExpr :: Int -> Expr -> String
The Expr datatype
Values of type Expr
represent objects or applications between objects.
Each object is encapsulated together with its type and string representation.
Values encoded in Expr
s are always monomorphic.
An Expr
can be constructed using:
val
, for values that areShow
instances;value
, for values that are notShow
instances, like functions;:$
, for applications betweenExpr
s.
> 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'
Show
ing 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 Expr
s usually follow the convention
where a value
whose String
representation starts with '_'
represents a var
iable.
Smart constructors
value :: Typeable a => String -> a -> Expr Source #
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]
($$) :: Expr -> Expr -> Maybe Expr Source #
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
var :: Typeable a => String -> a -> Expr Source #
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 ('_'
).
Evaluating Exprs
evaluate :: Typeable a => Expr -> Maybe a Source #
O(n).
Just
the value of an expression when possible (correct type),
Nothing
otherwise.
This does not catch errors from undefined
Dynamic
value
s.
> 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
eval :: Typeable a => a -> Expr -> a Source #
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
typ :: Expr -> TypeRep Source #
O(n). Computes the type of an expression. This raises errors, but this should not happen if expressions are smart-constructed.
> let one = val (1 :: Int) > let bee = val 'b' > let absE = value "abs" (abs :: Int -> Int)
> typ one Int
> typ bee Char
> typ absE Int -> Int
> typ (absE :$ one) Int
> typ (absE :$ bee) *** Exception: type mismatch, cannot apply `Int -> Int' to `Char'
> typ ((absE :$ bee) :$ one) *** Exception: type mismatch, cannot apply `Int -> Int' to `Char'
etyp :: Expr -> Either (TypeRep, TypeRep) TypeRep Source #
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)
toDynamic :: Expr -> Maybe Dynamic Source #
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
Boolean properties
isValue :: Expr -> Bool Source #
O(1).
Returns whether an Expr
is a terminal value (Value
).
> isValue $ var "x" (undefined :: Int) True
> isValue $ val False True
> isValue $ value "not" not :$ var "p" (undefined :: Bool) False
This is equivalent to pattern matching the Value
constructor.
Properties:
isValue (Value e) = True
isValue (e1 :$ e2) = False
isValue = not . isApp
isValue e = isVar e || isConst e
isApp :: Expr -> Bool Source #
O(1).
Returns whether an Expr
is an application (:$
).
> isApp $ var "x" (undefined :: Int) False
> isApp $ val False False
> isApp $ value "not" not :$ var "p" (undefined :: Bool) True
This is equivalent to pattern matching the :$
constructor.
Properties:
isApp (e1 :$ e2) = True
isApp (Value e) = False
isApp = not . isValue
isApp e = not (isVar e) && not (isConst e)
isIllTyped :: Expr -> Bool Source #
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
isWellTyped :: Expr -> Bool Source #
O(n).
Returns whether the given Expr
is well typed.
(cf. isIllTyped
)
> isWellTyped (absE :$ val (1 :: Int)) True
> isWellTyped (absE :$ val 'b') False
isGround :: Expr -> Bool Source #
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
Comparison
compareComplexity :: Expr -> Expr -> Ordering Source #
O(n).
Compares the complexity of two Expr
s.
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
Properties
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
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
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.
height :: Expr -> Int Source #
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.
Listing subexpressions
subexprs :: Expr -> [Expr] Source #
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 ]
values :: Expr -> [Expr] Source #
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 ]
vars :: Expr -> [Expr] Source #
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]
consts :: Expr -> [Expr] Source #
O(n).
List terminal constants in an expression in order and with repetitions.
(cf. nubConsts
)
> consts (xx -+- yy) [ (+) :: Int -> Int -> Int ]
> consts (xx -+- (yy -+- zz)) [ (+) :: Int -> Int -> Int , (+) :: Int -> Int -> Int ]
> consts (zero -+- (one -*- two)) [ (+) :: Int -> Int -> Int , 0 :: Int , (*) :: Int -> Int -> Int , 1 :: Int , 2 :: Int ]
> consts (pp -&&- true) [ (&&) :: Bool -> Bool -> Bool , True :: Bool ]
nubSubexprs :: Expr -> [Expr] Source #
Average O(n log n) for the spine, O(n^2) for full evaluation.
Lists all subexpressions of a given expression without repetitions.
This includes the expression itself and partial function applications.
(cf. subexprs
)
> nubSubexprs (xx -+- yy) [ x :: Int , y :: Int , (+) :: Int -> Int -> Int , (x +) :: Int -> Int , x + y :: Int ]
> nubSubexprs (pp -&&- (pp -&&- true)) [ p :: Bool , True :: Bool , (&&) :: Bool -> Bool -> Bool , (p &&) :: Bool -> Bool , p && True :: Bool , p && (p && True) :: Bool ]
While this is O(n log n) on average it is O(n^2) in the worst-case (f (g (h (i (j (k (l (m (n x))))))))).
nubValues :: Expr -> [Expr] Source #
O(n log n).
Lists all terminal values in an expression without repetitions.
(cf. values
)
> nubValues (xx -+- yy) [ x :: Int , y :: Int , (+) :: Int -> Int -> Int
]
> nubValues (xx -+- (yy -+- zz)) [ x :: Int , y :: Int , z :: Int , (+) :: Int -> Int -> Int ]
> nubValues (zero -+- (one -*- two)) [ 0 :: Int , 1 :: Int , 2 :: Int , (*) :: Int -> Int -> Int , (+) :: Int -> Int -> Int ]
> nubValues (pp -&&- pp) [ p :: Bool , (&&) :: Bool -> Bool -> Bool ]
nubVars :: Expr -> [Expr] Source #
O(n log n).
Lists all variables in an expression without repetitions.
(cf. vars
)
> nubVars (yy -+- xx) [ x :: Int , y :: Int ]
> nubVars (xx -+- (yy -+- xx)) [ x :: Int , y :: Int ]
> nubVars (zero -+- (one -*- two)) []
> nubVars (pp -&&- true) [p :: Bool]
nubConsts :: Expr -> [Expr] Source #
O(n log n).
List terminal constants in an expression without repetitions.
(cf. consts
)
> nubConsts (xx -+- yy) [ (+) :: Int -> Int -> Int ]
> nubConsts (xx -+- (yy -+- zz)) [ (+) :: Int -> Int -> Int ]
> nubConsts (pp -&&- true) [ True :: Bool , (&&) :: Bool -> Bool -> Bool ]
Other utilities
unfoldApp :: Expr -> [Expr] Source #
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]
showExpr :: Expr -> String Source #
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)