The typeparams library

This library provides a lens-like interface for working with type parameters. In the code:

data Example p1 (p2::Config Nat) (p3::Constraint) = Example

p1, p2, and p3 are the type parameters. The tutorial below uses unboxed vectors to demonstrate some of the library's capabilities. In particular, we'll see:

1. A type safe way to unbox your unboxed vectors. This technique gives a 25% speed improvement on nearest neighbor queries. The standard Vector class provided in Data.Vector.Generic can be used, so we retain all the stream fusion goodness.

2. A simple interface for supercompilation. In the example below, we combine this library and the fast-math library to get up to a 40x speed improvement when calculating the Lp distance between vectors.

Further documentation can be found on hackage, and examples with non-vector data types can be found in the examples folder. You can download the library from github directly, or via cabal:

cabal update
cabal install typeparams

Tutorial: unbox your unboxed vectors!

The remainder of this README is a literate haskell file. Please follow along yourself!

> import Control.Category
> import Data.Params
> import Data.Params.Vector.Unboxed 
> import qualified Data.Vector.Generic as VG
> import Prelude hiding ((.),id)

The Data.Params.Vector.Unboxed module contains the following definition for our vectors:

data family Vector (len::Config Nat) elem 
mkParams ''Vector

mkParams is a template haskell function that generates a number of useful functions and classes that will be described below. The len type param lets us statically enforce the size of a vector as follows:

> v1 = VG.fromList [1..10] :: Vector (Static 10) Float

Here, Static means that the parameter is known statically at compile time. If we don't know in advance the size of our vectors, however, we can set len to Automatic:

> v2 = VG.fromList [1..10] :: Vector Automatic Float

v2 will behave exactly like the unboxed vectors in the vector package.

The Config param generalizes the concept of implicit configurations introduced by this functional pearl by Oleg Kiselyov and Chung-chieh Shan. (See also the ImplicitParams GHC extension.) It can take on types of Static x, Automatic, or RunTime. This tutorial will begin by working through the capabilities of the Static configurations before discussing the other options.

From type params to values

We can get access to the value of the len parameter using the function:

viewParam :: ViewParam p t => TypeLens Base p -> t -> ParamType p

The singleton type TypeLens Base p identifies which parameter we are viewing in type t. The type lens we want is _len :: TypeLens Base Param_len. The value _len and type Param_len were created by the mkParams function above. The significance of Base will be explained in a subsequent section.

All together, we use it as:

ghci> viewParam _len v1
10

The viewParam function does not evaluate its arguments, so we could also call the function as:

ghci> viewParam _len (undefined::Vector (Static 10) Float)
10

We cannot use ViewParam if the length is being managed automatically. Vector Automatic Float is not an instance of the ViewParam type class, so the type checker enforces this restriction automatically.

Unboxing the vector

If we know a vector's size at compile time, then the compiler has all the information it needs to unbox the vector. Therefore, we can construct a 2d unboxed vector by:

> vv1 :: Vector (Static 2) (Vector (Static 10) Float)
> vv1 = VG.fromList [VG.fromList [1..10], VG.fromList [21..30]] 

or even a 3d vector by:

> vvv1 :: Vector (Static 20) (Vector (Static 2) (Vector (Static 10) Float))
> vvv1 = VG.replicate 20 vv1

In general, there are no limits to the depth the vectors can be nested.

###Viewing nested parameters

What if we want to view the length of a nested inner vector? The value _elem :: TypeLens p (Param_elem p) gives us this capability. It composes with _len to give the type:

_elem._len :: TypeLens Base (Param_elem Param_len)

_elem and Param_elem were also created by mkParams. In general, mkParams will generate these type lenses for every type param of its argument. If the type param p1 has kind *, then the type lens will have type _p1 :: TypeLens p (Param_p1 p) and the class will have kind Param_p1 :: (* -> Constraint) -> * -> Constraint. If the type param has any other kind (e.g. Config Nat), then mkParams will generate _p1 :: TypeLens Base Param_p1 and Param_p1 :: * -> Constraint.

The type of _elem allows us to combine it with _len to view the inner parameters of a type. Using the vectors we created above, we can view their parameters with:

ghci> viewParam _len vv1
2

ghci> viewParam (_elem._len) vv1
10

ghci> viewParam _len vvv1
20

ghci> viewParam (_elem._len) vvv1
2

ghci> viewParam (_elem._elem._len) vvv1
10

###Lensing into giant types

What if instead of having a Vector of Vectors, we have some other data type of Vectors? For example, what if we have a Maybe (Vector len elem). Now, how can we get access to the length of the vector?

Consider the definition of Maybe:

data Maybe a = Nothing | Just a

If we run the following template haskell:

> mkParams ''Maybe

then we will generate the type lens _a :: TypeLens p (Param_a p) which will give us the desired capability:

ghci> viewParam (_a._len) (undefined :: Maybe (Vector (Static 10) Int))
10

We can do the same process for any data type, even if the names of their type params overlap. For example, we can run:

> mkparams ''Either

This will reuse the already created _a type lens (which corresponds to the left component of Either) and generate the type lens _b :: TypeLens p (Param_b p) (which corresponds to the right component).

We can use type lenses in this fashion to extract parameters from truly monstrous types. For example, given the type:

> type Monster a = Either
>   (Maybe (Vector (Static 34) Float))
>   (Either 
>       a
>       (Either 
>           (Vector (Static 2) (Vector (Static 10) Double))
>           (Vector (Static 1) Int)
>       )
>   )

We can do:

ghci> viewParam (_a._a._len) (undefined::Monster Int)
34

ghci> viewParam (_b._b._a._elem._len) (undefined::Monster Float)
10

No matter how large the type is, we can compose TypeLenses to access any configuration parameter.

It would be nice if the type lenses for these built in data types had more meaningful names (like _just,_left, and _right), but this would require a change to base.

###From values back to type params

That's cool, but it's not super useful if we have to know the values of all our configurations at compile time. The RunTime and Automatic Config values give us more flexibility. We will see that the RunTime method is powerful but cumbersome, and the Automatic method will provide a much simpler interface that wraps the RunTime method.

(The RunTime configurations use the magic of the reflection package. The internal code is based off of Austin Seipp's excellent reflection tutorial.)

Whenever we need to specify a RunTime param, we use the function:

with1Param :: 
    ( ParamIndex p
    ) => TypeLens Base p -> ParamType p -> ((ApplyConstraint p m) => m) -> m

For example, we can specify the length of the innermost vector as follows:

> vvv2 :: Vector (Static 1) (Vector (Static 1) (Vector RunTime Float))
> vvv2 = with1Param (_elem._elem._len) 10 $ VG.singleton $ VG.singleton $ VG.fromList [1..10] 

Or we can specify the length of all vectors:

> vvv3 :: Vector RunTime (Vector RunTime (Vector RunTime Float))
> vvv3 = with1Param (_elem._elem._len) 10 
>      $ with1Param (_elem._len) 1 
>      $ with1Param _len 1 
>      $ VG.singleton $ VG.singleton $ VG.fromList [1..10] 

But wait! If we try to show either of these variables, we get an error message:

ghci> show vvv2
<interactive>:19:1:
    No instance for (Param_len (Vector 'RunTime Float))
      arising from a use of ‘print’
    In a stmt of an interactive GHCi command: print it

This is because RunTime configurations don't remember what value they were set to. Every time we use a variable with a RunTime configuration, we must manually specify the value.

The with1Param function is only useful when we pass parameters to the output of whatever function we are calling. In the example of show, however, we need to pass parameters to the input of the function. We do this using the function:

apWith1Param ::
  ( ValidIndex p
  ) => TypeLens Base p
    -> ParamType p
    -> ((ApplyConstraint p m) => m -> n)
    -> ((ApplyConstraint p m) => m)
    -> n

Similar functions exist for passing more than one parameter. These functions let us specify configurations to the arguments of a function. So if we want to show our vectors, we could call:

ghci> apWith1Param (_elem._elem._len) 10 show vvv2
"fromList [fromList [fromList [1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0]]]"

ghci> apWith3Param (_elem._elem._len) 10 (_elem._len) 1 _len 1 show vvv3
"fromList [fromList [fromList [1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0]]]"

A bug in GHC!

Unfortunately, due to a [bug in GHC 7.8.2's typechecker](h