Module Heap

This module defines a heap structure, containing bindings from variables to markers for free variables or black holes, or the expressions.

Author: Björn Peemöller, Jan Tikovsky

Version: October 2017

Summary of exported operations:

emptyH
                  ::  FM Int Binding

Create an empty heap

fromListH
                  ::  [(Int,Binding)] -> FM Int Binding

Create a heap from a list of bindings

isEmptyH
                  ::  FM Int Binding -> Bool

Check if heap is empty

elemH
                  ::  Int -> FM Int Binding -> Bool

Check if there is a binding for a variable in the heap

lookupH
                  ::  Int -> FM Int Binding -> Maybe Binding

Lookup a binding for a variable in the heap

bindH
                  ::  Int -> Binding -> FM Int Binding -> FM Int Binding

Bind a variable to a binding in the given heap

bindHole
                  ::  Int -> FM Int Binding -> FM Int Binding

Bind a variable as a "black hole" in the given heap

bindExpr
                  ::  Int -> AExpr (TypeExpr,Maybe Int,Bool) -> FM Int Binding -> FM Int Binding

Bind a variable to the given expression in the given heap

bindLazyExpr
                  ::  Int -> AExpr (TypeExpr,Maybe Int,Bool) -> FM Int Binding -> FM Int Binding

Bind a variable lazily to the given expression in the given heap

bindFree
                  ::  Int -> FM Int Binding -> FM Int Binding

Bind a variable as "free" in the given heap

bindLazyFree
                  ::  Int -> FM Int Binding -> FM Int Binding

Bind a variable lazily as "free" in the given heap

bindSym
                  ::  Int -> FM Int Binding -> FM Int Binding

Bind a variable as symbolic argument

unbind
                  ::  Int -> FM Int Binding -> FM Int Binding

Unbind a variable in the given heap

ppHeap
                  ::  FM Int Binding -> Doc

Exported datatypes:

Binding

A Binding represents the value of a variable bound in the heap.

Constructors:

BlackHole :: Binding : the variable is a black hole, such as in let x = x in x
BoundVar :: (AExpr TypeAnn) -> Binding : the variable is bound to an expression e
LazyBound :: (AExpr TypeAnn) -> Binding : the variable is bound to an expression e lazily
FreeVar :: Binding : the variable is a logic (free) variable
LazyFree :: Binding : the variable is a lazily bound logic (free) variable
SymArg :: Binding : the variable is a symbolic argument

Heap

A Heap is an association from a VarIndex to a Binding

Type synonym: Heap = FM VarIndex Binding

Exported operations:

emptyH :: FM Int Binding

Create an empty heap

fromListH :: [(Int,Binding)] -> FM Int Binding

Create a heap from a list of bindings

isEmptyH :: FM Int Binding -> Bool

Check if heap is empty

elemH :: Int -> FM Int Binding -> Bool

Check if there is a binding for a variable in the heap

lookupH :: Int -> FM Int Binding -> Maybe Binding

Lookup a binding for a variable in the heap

bindH :: Int -> Binding -> FM Int Binding -> FM Int Binding

Bind a variable to a binding in the given heap

bindHole :: Int -> FM Int Binding -> FM Int Binding

Bind a variable as a "black hole" in the given heap

bindExpr :: Int -> AExpr (TypeExpr,Maybe Int,Bool) -> FM Int Binding -> FM Int Binding

Bind a variable to the given expression in the given heap

bindLazyExpr :: Int -> AExpr (TypeExpr,Maybe Int,Bool) -> FM Int Binding -> FM Int Binding

Bind a variable lazily to the given expression in the given heap

bindFree :: Int -> FM Int Binding -> FM Int Binding

Bind a variable as "free" in the given heap

bindLazyFree :: Int -> FM Int Binding -> FM Int Binding

Bind a variable lazily as "free" in the given heap

bindSym :: Int -> FM Int Binding -> FM Int Binding

Bind a variable as symbolic argument

unbind :: Int -> FM Int Binding -> FM Int Binding

Unbind a variable in the given heap

ppHeap :: FM Int Binding -> Doc