Data.Generics.TH

This is the code for "Template Your Boilerplate" under review at the Haskell Symposium 2012.

A draft copy of that paper is available at http://cs.pdx.edu/~adamsmic/projects/tyb/TYB.pdf and provides more thorough documentation.

Primitives

thcase

Arguments

:: Quasi m

=> (m Exp -> [(Type, m Exp)] -> m Exp)

Case handling function. The first argument is the constructor. The second argument is the list of arguments and their types.

-> m Type

The type to inspect.

-> m Exp

The expression containing the case expression. If the type to inspect is t and the type of the Exp returned by the case handling function is r, the Exp returned by thcase is of type t -> r.

Case expression generation. This is the core function of the Template Your Boilerplate library.

This function is similar to thcase', except that since most users will note care about the distinction between types and primitive types, this function smooths over the differences by treating primitive types as types with nullary constructors.

thcase'

Arguments

:: Quasi m

=> (Either Name (Name, [(Type, Name)]) -> m Exp)

Case handling function. If the Type being inspected is a primitive type, argument is Left var where var is a variable bound to the case discriminant. Otherwise, argument is Right (ctor, args) where ctor is the constructor name and args is a list of the argument's types and the variable bound to the argument.

-> m Type

The type to inspect.

-> m Exp

The expression containing the case expression. If the type to inspect is t and the type of the Exp returned by the case handling function is r, the Exp returned by thcase' is of type t -> r.

Primitive case expression generation. Most users will want to use thcase instead.

thfoldl

Arguments

:: Quasi m

=> (m Exp -> Type -> m Exp -> m Exp)

Constructor argument application. If the first Exp is of type c (a -> b), the Type is a, and the second Exp is of type a, should return an Exp of type c b.

-> (m Exp -> m Exp)

Constructor injection. The argument Exp will be one of the constructors from the type to be inspected. If the argument Exp is of type a, should return an Exp of type c a.

-> m Type

The type to inspect.

-> m Exp

The expression containing the case expression. If the type to inspect is t and the type of the Exp returned by the case handling function is c t, the Exp returned by thcase is of type t -> c t.

Scrap Your Boilerplate style case expression generation. The thcase function is generally simpler to use instead of this and is more powerful.

Single-layer traversals

thmapT

Arguments

:: Quasi m

=> (Type -> m Exp)

The transformation. If the Type is t, must return an Exp of type t -> t.

-> m Type -> m Exp

Generates an Exp that applies the transformation to each immediate child. If Type is t0, returns an Exp of type t0 -> t0.

Generic single-layer transformation

thmapM

Arguments

:: Quasi m

=> (Type -> m Exp)

The monadic transformation. If the Type is t, must return an Exp of type t -> m t

-> m Type -> m Exp

Generates an Exp that applies the monadic transformation to each immediate child. If the Type is t0, returns an Exp of type t0 -> m t0.

Generic single-layer monadic transformation.

thmapQ

Arguments

:: Quasi m

=> (Type -> m Exp)

The query. Extracts data from the given type. If the Type is t, must return an Exp of type t -> a.

-> m Type -> m Exp

Generates an Exp that applies the query to each immediate child. If the Type is t0, returns an Exp of type t0 -> [a].

Generic single-layer query.

thmapQl

Arguments

:: Quasi m

=> m Exp

Combining function. Exp must have type r -> r' -> r

-> m Exp

Starting value. Exp must have type r.

-> (Type -> m Exp)

The query. Extract data from the given type. If the Type is t, must return an Exp of type t -> r'.

-> m Type -> m Exp

Generates an Exp that applies the query to each immediate child and uses the starting value and combining functions to fold the query results. If the Type is t0, returns an Exp of type t0 -> r.

Generic single-layer query (left associative).

thmapQr

Arguments

:: Quasi m

=> m Exp

Combining function. Exp must have type r' -> r -> r

-> m Exp

Starting value. Exp must have type r.

-> (Type -> m Exp)

The query. Extract data from the given type. If the Type is t, must return an Exp of type t -> r'.

-> m Type -> m Exp

Generates an Exp that applies the query to each immediate child and uses the starting value and combining functions to fold the query results. If the Type is t0, returns an Exp of type t0 -> r.

Generic single-layer query (right associative).

Memoization

memoizeDec

Arguments

:: (Quasi m, Ord a)

=> ((a -> m Exp) -> a -> m Exp)

The function to memoize. Takes a memoized version of the function as argument.

-> a

The initial argument to the function.

-> m ([Dec], Exp)

The result of applying the function to the initial argument. The |Exp| is the result, but expects the [Dec] to be in scope.

Memoizes a code generation function. Most users will want to use memoizeExp instead as it provides a simplified interface, but all the notes about this function also apply to memoizeExp.

We memoize a function returning an Exp by creating a Dec with a body that is the Exp returned by that function. The return value of the function is replaced with a VarE that refers to the Dec. This allows functions like everywhere to avoid infinite recursions when they traverse recursive types like lists.

The memoization functions come in two flavors: memoizeDec and memoizeExp. With memoizeDec it is the responsibility of the caller to place the Dec in an appropriate place. The memoizeExp function automatically handles the Dec by wrapping them in a local LetE form.

Every memoized function is passed a memoized version of itself. This is the function that should be used in recursive calls. Failing to do so will prevent those calls from being memoized.

Mutually recursive functions are possible using memoizeDec2, etc. and memoizeExp2, etc.

If the function being memoized needs to accept multiple arguments, then they must be packed into a tuple and passed as a single argument.

Effects in the m monad are only performed the first time the memoized function is called with a particular argument. Subsequent times the monad is simply the result of a return. Thus while it is tempting to store extra return values in the monad, this should be avoided due to the high likelihood of unexpected behavior.

Implementation Notes:

• Note that m should not store a copy of the function, otherwise a memory leak is introduced. It wouldn't even make sense to do it anyway since the results refer to expressions that might not be in scope.
• The memoized function stores a reference to the memoization table, Thus if a reference to the memoized function gets tucked inside m, then a memory leak can be introduced. We could eliminate this leak by clearing and invalidating the table when memoizeDec returns. To fully do this properly the table would have to be invalidated in such a way that the memoized version of the function would not continue to try populating the table if the user called it after memoizeDec return.
• Conceptually we should use a State monad instead of an IORef but we choose IORef since we can embed IO operations in a Quasi without imposing extra restrictions on m.
• Other designs are possible. This design was choosen for its simplicity of use. The choice of memoization interface is largely orthogonal to the rest of this library.
• Type synonyms and kind annotations may lead to duplicate versions of the code (e.g. versions for both String and [Char]) Usually this isn't a problem, but if it is, then the type synonyms should be expanded before each call to the memoized function.
• GADTs and data/type families haven't been considered in this code. It is unknown whether they work.

Note that polymorphically recursive types (e.g. data F a = N a | F (F (Int, a))) have an infinite number of types in them and thus despite memoization this function will not terminate on those types.

memoizeDec2

Arguments

:: (Quasi m, Ord a, Ord b)

=> ((a -> m Exp) -> (b -> m Exp) -> a -> m Exp)

The first function to memoize. Takes memoized versions of the two functions as arguments.

-> ((a -> m Exp) -> (b -> m Exp) -> b -> m Exp)

The second function to memoize. Takes memoized versions of the two functions as arguments.

-> a

The initial argument.

-> m ([Dec], Exp)

The result of applying the function to the initial argument. The |Exp| is the result, but expects the [Dec] to be in scope.

Simultaneously memoizes two code generation functions. All of the notes about memoizeDec also apply to this function. Most users will want to use memoizeExp2 instead of this function as it provides a simplified interface.

memoizeExp :: (Quasi m, Ord a) => ((a -> m Exp) -> a -> m Exp) -> a -> m Exp

Memoizes a code generation function. Behaves identically to memoizeDec except that it returns a LetE that binds the Dec resulting from memoizeDec for the Exp resulting from memoizeDec.

memoizeExp2 :: (Quasi m, Ord a, Ord b) => ((a -> m Exp) -> (b -> m Exp) -> a -> m Exp) -> ((a -> m Exp) -> (b -> m Exp) -> b -> m Exp) -> a -> m Exp

Simultaneously memoizes two code generation functions. Behaves identically to memoizeDec2 except that it returns a LetE that binds the Dec resulting from memoizeDec2 for the Exp resulting from memoizeDec2.

Traversals

Transformations

everywhere

Arguments

:: Quasi m

=> (Type -> m Exp)

The transformation. If the Type is t, must return an Exp of type t -> t.

-> m Type -> m Exp

Generates an Exp that applies the transformation to each descendant. If Type is t0, returns an Exp of type t0 -> t0.

Generic recursive transformation (bottom-up)

everywhere'

Arguments

:: Quasi m

=> (Type -> m Exp)

The transformation. If the Type is t, must return an Exp of type t -> t.

-> m Type -> m Exp

Generates an Exp that applies the transformation to each descendant. If Type is t0, returns an Exp of type t0 -> t0.

Generic recursive transformation (top-down)

everywhereBut

Arguments

:: Quasi m

=> (Type -> m Bool)

The query. Should return True when a given type should not be traversed.

-> (Type -> m Exp)

The transformation. If the Type is t, must return an Exp of type t -> t.

-> m Type -> m Exp

Generates an Exp that applies the transformation to each descendant (except for parts skipped due to the query returning True). If the Type is t0, returns an Exp of type t0 -> t0.

Generic recursive transformation (bottom-up) with selective traversal. Skips traversal when a given query returns True.

everywhereM

Arguments

:: Quasi m

=> (Type -> m Exp)

The monadic transformation. If the Type is t, must return an Exp of type t -> m t.

-> m Type -> m Exp

Generates an Exp that applies the transformation to each descendant. If Type is t0, returns an Exp of type t0 -> m t0.

Generic recursive monadic transformation (bottom-up)

everywhereM'

Arguments

:: Quasi m

=> (Type -> m Exp)

The monadic transformation. If the Type is t, must return an Exp of type t -> m t.

-> m Type -> m Exp

Generates an Exp that applies the transformation to each descendant. If Type is t0, returns an Exp of type t0 -> m t0.

Generic recursive monadic transformation (top-down)

everywhereButM'

Arguments

:: Quasi m

=> (Type -> m Bool)

The query. Should return True when a given type should not be traversed.

-> (Type -> m Exp)

The monadic transformation. If the Type is t, must return an Exp of type t -> m t.

-> m Type -> m Exp

Generates an Exp that applies the monadic transformation to each descendant (except for parts skipped due to the query returning True). If the Type is t0, returns an Exp of type t0 -> m t0.

Generic recursive monadic transformation (top-down) with selective traversal. Skips traversal when a given query returns True.

everywhereFor

Arguments

:: Quasi m

=> Name

Name of a function of type t -> t

-> m Type -> m Exp

Generates an Exp that applies the transformation to each descendant that is of type t. If the Type is t0, returns an Exp of type t0 -> t0.

Generic recursive transformation (bottom-up) with selective traversal. Recurs on only types that can contain a type with type specific behavior.

everywhereForM

Arguments

:: Quasi m

=> Name

Name of a function of type t -> m t

-> m Type -> m Exp

Generates an Exp that applies the monadic transformation to each descendant that is of type t. If the Type is t0, returns an Exp of type t0 -> m t0.

Generic recursive monadic transformation (bottom-up) with selective traversal. Recurs on only types that can contain a type with type specific behavior.

somewhere

Arguments

:: Quasi m

=> ((Type -> m Exp) -> Type -> m (Maybe Exp))

The transformation. The first argument is the memoized recursion. If Nothing is returned, then the standard, automatic recursion is done. If Just is returned, then no automatic recursion is done and the resulting Exp is used at that type. In that case, if further recursion is desired, then the expression should include a call to the memoized recursion. If the Type is t, then the returned Exp must be of type t -> t.

We use Maybe instead of MonadPlus to avoid the user having to play games with runMaybeT and so forth.

-> m Type -> m Exp

Generates an Exp that applies the transformation to each descendant. If Type is t0, returns an Exp of type t0 -> t0.

Generic recursive transformation (bottom-up) with selective traversal.

somewhereM

Arguments

:: Quasi m

=> ((Type -> m Exp) -> Type -> m (Maybe Exp))

The monadic transformation. The first argument is the memoized recursion. If Nothing is returned, then the standard, automatic recursion is done. If Just is returned, then no automatic recursion is done and the resulting Exp is used at that type. In that case, if further recursion is desired, then the expression should include a call to the memoized recursion. If the Type is t, then the returned Exp must be of type t -> m t.

We use Maybe instead of MonadPlus to avoid the user having to play games with runMaybeT and so forth.

-> m Type -> m Exp

Generates an Exp that applies the transformation to each descendant. If Type is t0, returns an Exp of type t0 -> m t0.

Generic recursive monadic transformation (bottom-up) with selective traversal.

Queries

everything

Arguments

:: Quasi m

=> m Exp

Combining function. Exp must have type r -> r -> r.

-> (Type -> m Exp)

The query. Extract data from the given type. If the Type is t, must return an Exp of type t -> r'.

-> m Type -> m Exp

Generates an Exp that applies the query to each descendant and uses the combining function to combine the query results. If the Type is t0, returns an Exp of type t0 -> r.

Generic recursive query (bottom-up).

everythingBut

Arguments

:: Quasi m

=> m Exp

Combining function. Exp must have type r -> r -> r.

-> (Type -> m (Exp, Bool))

The query, combining, selectivity function. If the Type is t, must return an Exp of type t -> r -> r. If the Bool is True the traversal does not proceed further into the recursion.

-> m Type -> m Exp

Generates an Exp that applies the query to each decendant. If Type is t0, returns an Exp of type t0 -> r

Generic recursive query with selective traversal

everythingAccL

Arguments

:: (Type -> Q Exp)

The query and combining function. If the Type is t, must return an Exp of type t -> r -> r.

-> Q Type -> Q Exp

Generates an Exp that applies the query to each decendant. If Type is t0, returns an Exp of type t0 -> r -> r

Generic recursive query with left-associative accumulation.

everythingAccL'

Arguments

:: (Type -> Q Exp)

The query and combining function. If the Type is t, must return an Exp of type t -> r -> r.

-> Q Type -> Q Exp

Generates an Exp that applies the query to each decendant. If Type is t0, returns an Exp of type t0 -> r -> r

Generic recursive query with strict left-associative accumulation

everythingButAccL

Arguments

:: (Type -> Q (Exp, Bool))

The query, combining, selectivity function. If the Type is t, must return an Exp of type t -> r -> r. If the Bool is True the traversal does not proceed further into the recursion.

-> Q Type -> Q Exp

Generates an Exp that applies the query to each decendant. If Type is t0, returns an Exp of type t0 -> r -> r

Generic recursive query with left-associative accumulation and selective traversal

everythingButAccL'

Arguments

:: (Type -> Q (Exp, Bool))

The query, combining, selectivity function. If the Type is t, must return an Exp of type t -> r -> r. If the Bool is True the traversal does not proceed further into the recursion.

-> Q Type -> Q Exp

Generates an Exp that applies the query to each decendant. If Type is t0, returns an Exp of type t0 -> r -> r

Generic recursive query with strict left-associative accumulation and selective traversal

everythingAccR

Arguments

:: (Type -> Q Exp)

The query and combining function. If the Type is t, must return an Exp of type t -> r -> r.

-> Q Type -> Q Exp

Generates an Exp that applies the query to each decendant. If Type is t0, returns an Exp of type t0 -> r -> r

Generic recursive query with right-associative accumulation

everythingButAccR

Arguments

:: (Type -> Q (Exp, Bool))

The query, combining, selectivity function. If the Type is t, must return an Exp of type t -> r -> r. If the Bool is True the traversal does not proceed further into the recursion.

-> Q Type -> Q Exp

Generates an Exp that applies the query to each decendant. If Type is t0, returns an Exp of type t0 -> r -> r

Generic recursive query with right-associative accumulation and selective traversal

everythingForR

Arguments

:: Name

Name of a function of type t -> r -> r

-> Q Type -> Q Exp

Generates an Exp that applies the query to each decendant that is of type t. If Type is t0, returns an Exp of type t0 -> r -> r

Generic recursive traversal using right-associative accumulation

everythingForL

Arguments

:: Name

Name of a function of type t -> r -> r

-> Q Type -> Q Exp

Generates an Exp that applies the query to each decendant that is of type t. If Type is t0, returns an Exp of type t0 -> r -> r

Generic recursive traversal using left-associative accumulation

everythingForL'

Arguments

:: Name

Name of a function of type t -> r -> r

-> Q Type -> Q Exp

Generates an Exp that applies the query to each decendant that is of type t. If Type is t0, returns an Exp of type t0 -> r -> r

Generic recursive traversal using strict left-associative accumulation

Extentions and adaptors

extN

Arguments

:: Quasi m

=> (Type -> m Exp)

The operation to be extended.

-> Name

Name of the function implementing the type specific behavior.

-> Type -> m Exp

The result of extending the operation. If the Name has type t -> s, then the extended operation has type specific behavior at t. At other types it behaves as the original operation.

Extends a generic operation with type specific behavior based on the type of the given name.

extE

Arguments

:: Quasi m

=> (Type -> m exp)

The operation to be extended.

-> (Type -> m Bool, m exp)

The fst of the pair should return True on types for which the operation should be extended. The snd of the pair is the expression to use on those types.

-> Type -> m exp

The result of extending the operation.

Extends a generic operation with type specific behavior.

extE'

Arguments

:: Quasi m

=> (Type -> m exp)

The operation to be extended.

-> (Type -> m Bool, Type -> m exp)

The fst of the pair should return True on types for which the operation should be extended. The snd of the pair when given one of these Types should return the expression to use on that type.

-> Type -> m exp

The result of extending the operation.

Extends a generic operation with type specific behavior.

mkT

Arguments

:: Quasi m

=> Name

Name of a function of type t -> t

-> Type -> m Exp

The generic transformation. If the Type is t0, then the Exp has type t0 -> t0. The Exp is the named function at t, and id elsewhere.

Makes a transformation from a named function.

mkTs

Arguments

:: Quasi m

=> [Name]

Names of functions of type t -> t for various t.

-> Type -> m Exp

The generic transformation. If the Type is t0, then the Exp has type t0 -> t0. If one of the named functions matches t0, then Exp is that function. Otherwise, it is id.

Makes a transformation from several named functions.

mkQ

Arguments

:: Quasi m

=> m Exp

Default value to return on types other than t. The Exp must be of type r.

-> Name

Name of a function of type t -> r

-> Type -> m Exp

The generic transformation. If the Type is t0, then the Exp has type t0 -> r. The Exp is the named function at t, and the provided default value elsewhere.

Makes a query from a named function.

mkQs

Arguments

:: Quasi m

=> m Exp

Default value to return on types that do not match the t from any named function. The Exp must be of type r.

-> [Name]

Names of functions of type t -> r for various t.

-> Type -> m Exp

The generic query. If the Type is t0, then the Exp has type t0 -> r. If one of the named functions matches t0, then Exp is that function. Otherwise, it is const of the provided default value.

Makes a query from several named functions.

mkM

Arguments

:: Quasi m

=> Name

Name of a function of type t -> m t

-> Type -> m Exp

The generic monadic transformation. If the Type is t0, then the Exp has type t0 -> m t0. The Exp is the named function at t, and return elsewhere.

Makes a monadic transformation from a named function.

mkMs

Arguments

:: Quasi m

=> [Name]

Names of functions of type t -> m t for various t.

-> Type -> m Exp

The generic monadic transformation. If the Type is t0, then the Exp has type t0 -> m t0. If one of the named functions matches t0, then Exp is that function. Otherwise, it is return.

Makes a monadic transformation from several named functions.

Type manipulation functions

eqType :: Quasi m => m Type -> Type -> m Bool

Tests if two types are equal modulo type synonyms and kind annotations. Naive equality would fail to equate String and [Char].

eqTypes :: Quasi m => [m Type] -> Type -> m Bool

Test if any of a list of types is equal to a particular type modulo type synonyms and kind annotations. Useful when multiple types share the same type-specific behavior.

inType :: Quasi m => m Type -> Type -> m Bool

inType t1 t2 = True iff t1 is (even recursively) inside t2

inTypes :: Quasi m => [m Type] -> Type -> m Bool

inTypes ts t2 = True iff any of ts is (even recursively) inside t2

constructorsOf :: Quasi m => Type -> m (Maybe [(Name, [Type])])

Returns the constructors of a given type. Returns Nothing if the type is primitive.

typeOfName :: Quasi m => Name -> m Type

Returns the type of a variable, method or constructor name.