ifcxt

Last updated: 2016-02-03 16:23:05 +0000

Upstream URL: git clone http://chriswarbo.net/git/ifcxt.git

Repo

View repository

View issue tracker

Contents of README.md follows


IfCxt

This package introduces the function:

<pre><code>ifCxt :: IfCxt cxt => proxy cxt -> (cxt => a) -> a -> a</code></pre>

This function acts like an <code>if</code> statement where the <code>proxy cxt</code> parameter is the condition. If the type checker can satisfy the <code>cxt</code> constraint, then the second argument <code>cxt => a</code> is returned; otherwise, the third argument <code>a</code> is returned.

Before seeing more details about how <code>ifCxt</code> is implemented, let's look at three examples of how to use it.

Example 1: show every type

The <code>cxtShow</code> function below is polymorphic over the type <code>a</code>. If <code>a</code> is an instance of <code>Show</code>, then <code>cxtShow a</code> evaluates to <code>show a</code>; but if <code>a</code> is not an instance of <code>Show</code>, <code>cxtShow a</code> evaluates to <code><<unshowable>></code>.

<pre><code>cxtShow :: forall a. IfCxt (Show a) => a -> String cxtShow a = ifCxt (Proxy::Proxy (Show a)) (show a) "<<unshowable>>"</code></pre>

In ghci:

<pre><code>ghci> cxtShow (1 :: Int) "1"</code></pre> <pre><code>ghci> cxtShow (id :: a -> a) "<<unshowable>>"</code></pre>

Example 2: make your code asymptotically efficient

The <code>nub</code> function removes duplicate elements from lists. It can be defined as:

<pre><code>nub :: Eq a => [a] -> [a] nub [] = [] nub (x:xs) = x : nub (filter (x/=) xs)</code></pre>

This function takes time O(n^2). But if we also have an <code>Ord</code> constraint, we can define a much more efficient version that takes time O(n log n):

<pre><code>nubOrd :: Ord a => [a] -> [a] nubOrd = go . sort where go (x1:x2:xs) | x1==x2 = go (x2:xs) | otherwise = x1 : go (x2:xs) go [x] = [x] go [] = []</code></pre>

Now, we can use the <code>ifCxt</code> function to define a version of <code>nub</code> that will automatically select the most efficient implementation for whatever type we happen to run it on:

<pre><code>cxtNub :: forall a. (Eq a, IfCxt (Ord a)) => [a] -> [a] cxtNub = ifCxt (Proxy::Proxy (Ord a)) nubOrd nub</code></pre>

Example 3: make your code numerically stable

The simplest way to sum a list of numbers is:

<pre><code>sumSimple :: Num a => [a] -> a sumSimple = foldl' (+) 0</code></pre>

This method has numerical stability issues on floating point representations. Kahan summation is a more accurate technique shown below:

<pre><code>sumKahan :: Num a => [a] -> a sumKahan = snd . foldl' go (0,0) where go (c,t) i = ((t'-t)-y,t') where y = i-c t' = t+y</code></pre>

Because Kahan summation does a lot more work than simple summation, we would prefer not to run it on non-floating point types. The <code>sumCxt</code> function below accomplishes this:

<pre><code>cxtSum :: forall a. (Num a, IfCxt (Floating a)) => [a] -> a cxtSum = ifCxt (Proxy::Proxy (Floating a)) sumKahan sumSimple</code></pre>

Notice that the <code>ifCxt</code> function is conditioning on the <code>Floating a</code> constraint, which isn't actually <em>used</em> by the <code>sumKahan</code> function.

How it works

The magic of the technique is in the <code>IfCxt</code> class:

<pre><code>class IfCxt (cxt :: Constraint) where ifCxt :: proxy cxt -> (cxt => a) -> a -> a</code></pre>

(Notice that making a constraint an instance of a class requires the<code>ConstraintKinds</code> extension, and the higher order <code>(cxt => a)</code> parameter requires the <code>RankNTypes</code> extension.)

There is a "global" instance defined as:

<pre><code>instance {-# OVERLAPPABLE #-} IfCxt cxt where ifCxt _ t f = f</code></pre>

What this says is that if no more specific instance is available, then the "global" <code>ifCxt</code> function will be used, which always returns the <code>f</code> (false) parameter.

Then for every instance of every other class, we need to define an overlapping <code>IfCxt</code> instance that always returns the <code>t</code> (true) parameter. For example, for <code>Show Int</code>, we define:

<pre><code>instance {-# OVERLAPS #-} IfCxt (Show Int) where ifCxt _ t f = t</code></pre>

This is a lot of boilerplate, so the template haskell function <code>mkIfCxtInstances</code> can be used to define these instances automatically. Unfortunately, due to a bug in template haskell we cannot enumerate all the classes currently in scope. So you must manually call <code>mkIfCxtInstances</code> on each class you want <code>ifCxt</code> to work with.