Data.Express.Core

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.

The Expr datatype

data Expr

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.

Constructors

Value String Dynamic

a value enconded as String and Dynamic

Expr :$ Expr

function application between expressions

Instances

Eq Expr

O(n). Does not evaluate values when comparing, but rather uses their representation as strings and their types.

This instance works for ill-typed expressions.

Defined in Data.Express.Core

Methods

(==) :: Expr -> Expr -> Bool

(/=) :: Expr -> Expr -> Bool

Ord Expr

O(n). Does not evaluate values when comparing, but rather uses their representation as strings and their types.

This instance works for ill-typed expressions.

Expressions come first when they have smaller complexity (compareComplexity) or when they come first lexicographically (compareLexicographically).

Defined in Data.Express.Core

Methods

compare :: Expr -> Expr -> Ordering

(<) :: Expr -> Expr -> Bool

(<=) :: Expr -> Expr -> Bool

(>) :: Expr -> Expr -> Bool

(>=) :: Expr -> Expr -> Bool

max :: Expr -> Expr -> Expr

min :: Expr -> Expr -> Expr

Show Expr

Shows Exprs with their types.

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

Defined in Data.Express.Core

Methods

showsPrec :: Int -> Expr -> ShowS

show :: Expr -> String

showList :: [Expr] -> ShowS

Smart constructors

value :: Typeable a => String -> a -> 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]

val :: (Typeable a, Show a) => 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

($$) :: Expr -> Expr -> Maybe 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

var :: Typeable a => String -> a -> 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 ('_').

Evaluating Exprs

evaluate :: Typeable a => Expr -> Maybe a

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

eval :: Typeable a => a -> Expr -> 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

evl :: Typeable 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.

typ :: Expr -> TypeRep

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'

etyp :: Expr -> Either (TypeRep, TypeRep) 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)

mtyp :: Expr -> Maybe 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

toDynamic :: Expr -> Maybe Dynamic

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

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

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)

isVar :: 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

isConst :: 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

isIllTyped :: 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

isWellTyped :: 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

isFun :: 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

hasVar :: 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

isGround :: 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

Comparison

compareComplexity :: Expr -> Expr -> Ordering

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:

1. e1 is smaller in size/length than e2, e.g.: x + y < x + (y + z);
2. or, e1 has more distinct variables than e2, e.g.: x + y < x + x;
3. or, e1 has more variable occurrences than e2, e.g.: x + x < 1 + x;
4. 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.

compareLexicographically :: 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.

compareQuickly :: 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.

Properties

arity :: Expr -> Int

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

size :: 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

depth :: 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.

height :: 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.

Listing subexpressions

subexprs :: Expr -> [Expr]

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]

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]

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]

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]

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))))).

nubValues :: 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))))).

nubVars :: 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))))).

nubConsts :: 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))))).

Other utilities

unfoldApp :: 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]

showExpr :: Expr -> String

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)

showOpExpr :: String -> 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)"

showPrecExpr :: Int -> Expr -> String

O(n). Like showExpr but allows specifying the surrounding precedence.

> showPrecExpr 6 (one -+- two)
"1 + 2"

> showPrecExpr 7 (one -+- two)
"(1 + 2)"