express-1.0.10: Dynamically-typed expressions involving function application and variables.
Copyright(c) 2019-2021 Rudy Matela
License3-Clause BSD (see the file LICENSE)
MaintainerRudy Matela <rudy@matela.com.br>
Safe HaskellSafe-Inferred
LanguageHaskell2010

Data.Express.Hole

Description

Utilities for manipulating variables and typed holes encoded as Exprs.

Synopsis

Creating variables

varAsTypeOf :: String -> Expr -> Expr Source #

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

listVars :: Typeable a => String -> a -> [Expr] Source #

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
, ...
]

listVarsAsTypeOf :: String -> Expr -> [Expr] Source #

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
, ...
]

Typed holes

hole :: Typeable a => a -> Expr Source #

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

isHole :: Expr -> Bool Source #

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

hasHole :: Expr -> Bool Source #

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

isComplete :: Expr -> Bool Source #

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.

holes :: Expr -> [Expr] Source #

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]

nubHoles :: Expr -> [Expr] Source #

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

holeAsTypeOf :: Expr -> Expr Source #

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

fill :: Expr -> [Expr] -> Expr Source #

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