ifcxt: 8c260e8de5222b62b0cbbd16f93d1ff8b5854d68

     1: # IfCxt
     2: 
     3: This package introduces the function:
     4: ```
     5: ifCxt :: IfCxt cxt => proxy cxt -> (cxt => a) -> a -> a
     6: ```
     7: This function acts like an `if` statement where the `proxy cxt` parameter is the condition.
     8: If the type checker can satisfy the `cxt` constraint, then the second argument `cxt => a` is returned;
     9: otherwise, the third argument `a` is returned.
    10: 
    11: Before seeing more details about how `ifCxt` is implemented,
    12: let's look at three examples of how to use it.
    13: 
    14: ### Example 1: show every type
    15: 
    16: The `cxtShow` function below is polymorphic over the type `a`.
    17: If `a` is an instance of `Show`, then `cxtShow a` evaluates to `show a`;
    18: but if `a` is not an instance of `Show`, `cxtShow a` evaluates to `<<unshowable>>`.
    19: 
    20: ```
    21: cxtShow :: forall a. IfCxt (Show a) => a -> String
    22: cxtShow a = ifCxt (Proxy::Proxy (Show a))
    23:     (show a)
    24:     "<<unshowable>>"
    25: ```
    26: In ghci:
    27: 
    28: ```
    29: ghci> cxtShow (1 :: Int)
    30: "1"
    31: ```
    32: ```
    33: ghci> cxtShow (id :: a -> a)
    34: "<<unshowable>>"
    35: ```
    36: 
    37: ### Example 2: make your code asymptotically efficient
    38: 
    39: The `nub` function removes duplicate elements from lists.
    40: It can be defined as:
    41: 
    42: ```
    43: nub :: Eq a => [a] -> [a]
    44: nub []     =  []
    45: nub (x:xs) =  x : nub (filter (x/=) xs)
    46: ```
    47: This function takes time O(n^2).
    48: But if we also have an `Ord` constraint, we can define a much more efficient version that takes time O(n log n):
    49: 
    50: ```
    51: nubOrd :: Ord a => [a] -> [a]
    52: nubOrd = go . sort
    53:     where
    54:         go (x1:x2:xs)
    55:             | x1==x2    =      go (x2:xs)
    56:             | otherwise = x1 : go (x2:xs)
    57:         go [x] = [x]
    58:         go []  = []
    59: ```
    60: Now, we can use the `ifCxt` function to define a version of `nub` that will automatically select the most efficient implementation for whatever type we happen to run it on:
    61: 
    62: ```
    63: cxtNub :: forall a. (Eq a, IfCxt (Ord a)) => [a] -> [a]
    64: cxtNub = ifCxt (Proxy::Proxy (Ord a)) nubOrd nub
    65: ```
    66: 
    67: ### Example 3: make your code numerically stable
    68: 
    69: The simplest way to sum a list of numbers is:
    70: ```
    71: sumSimple :: Num a => [a] -> a
    72: sumSimple = foldl' (+) 0
    73: ```
    74: This method has numerical stability issues on floating point representations.
    75: [Kahan summation](https://en.wikipedia.org/wiki/Kahan_summation_algorithm) is a more accurate technique shown below:
    76: ```
    77: sumKahan :: Num a => [a] -> a
    78: sumKahan = snd . foldl' go (0,0)
    79:     where
    80:         go (c,t) i = ((t'-t)-y,t')
    81:             where
    82:                 y = i-c
    83:                 t' = t+y
    84: ```
    85: Because Kahan summation does a lot more work than simple summation, we would prefer not to run it on non-floating point types.
    86: The `sumCxt` function below accomplishes this:
    87: ```
    88: cxtSum :: forall a. (Num a, IfCxt (Floating a)) => [a] -> a
    89: cxtSum = ifCxt (Proxy::Proxy (Floating a)) sumKahan sumSimple
    90: ```
    91: Notice that the `ifCxt` function is conditioning on the `Floating a` constraint,
    92: which isn't actually *used* by the `sumKahan` function.
    93: 
    94: ## How it works
    95: 
    96: The magic of the technique is in the `IfCxt` class:
    97: ```
    98: class IfCxt (cxt :: Constraint) where
    99:     ifCxt :: proxy cxt -> (cxt => a) -> a -> a
   100: ```
   101: (Notice that making a constraint an instance of a class requires the`ConstraintKinds` extension,
   102: and the higher order `(cxt => a)` parameter requires the `RankNTypes` extension.)
   103: 
   104: There is a "global" instance defined as:
   105: ```
   106: instance {-# OVERLAPPABLE #-} IfCxt cxt where ifCxt _ t f = f
   107: ```
   108: What this says is that if no more specific instance is available, then the "global" `ifCxt` function will be used, which always returns the `f` (false) parameter.
   109: 
   110: Then for every instance of every other class, we need to define an overlapping `IfCxt` instance that always returns the `t` (true) parameter.
   111: For example, for `Show Int`, we define:
   112: ```
   113: instance {-# OVERLAPS #-} IfCxt (Show Int) where ifCxt _ t f = t
   114: ```
   115: 
   116: This is a lot of boilerplate, so the template haskell function `mkIfCxtInstances` can be used to define these instances automatically.
   117: Unfortunately, due to a [bug in template haskell](https://ghc.haskell.org/trac/ghc/ticket/9699) we cannot enumerate all the classes currently in scope.
   118: So you must manually call `mkIfCxtInstances` on each class you want `ifCxt` to work with.