Last updated: 2016-08-03 14:49:53 -0700
Upstream URL: git clone http://chriswarbo.net/git/ifcxt.git
Contents of README.md follows
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.
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>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>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.
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.