[Haskell-cafe] A new type of newtype --- Type-level instance diversification and resolution (tl; dr)

[Albert Y. C. Lai]

When you store elements in a binary search tree, wouldn't you love to 
custom-order the comparison order? Wouldn't you love to do so without 
newtype-wrapping the element type? In fact you may actually opine that 
your element type should not admit a standard order in the first place 
(e.g., complex numbers), and whichever order used for the sake of binary 
search trees should stay just that and not become a general-purpose default.

Perhaps more pressing to most people is when you store elements in a 
HashSet and you want to customize the hash function, again without 
either newtype-wrapping or fighting over defaults.

Here is how to do that.

Have a parameterized Ord class like this:

{-# LANGUAGE MultiParamTypeClasses, PolyKinds, KindSignatures #-}

class MyOrd (resolver :: k) a where
     mycmp :: p resolver -> a -> a -> Ordering

instance MyOrd () Int where
     mycmp _ x y = compare x y

data Rev

instance MyOrd Rev Int where
     mycmp _ x y = compare y x

It is also possible to get rid of the proxy parameter and use 
TypeApplication instead.

dmwit from IRC suggests that MyOrd could be tied back to standard Ord by:

instance MyOrd () a => Ord a

which helps with backward compatibility. So basically use () to resolve 
to the standard instances (wherever a community-wide standard makes 
sense) and have existing standard classes tied to the new parameterized 
classes by resolver ~ ().

Now use the parameterized Ord class for binary search trees:

{-# LANGUAGE ScopedTypeVariables #-}
import Data.Proxy(Proxy(Proxy))
import Data.List(foldl')

data BST (resolver :: k) a = Nil | Bin !(BST resolver a) a !(BST resolver a)

empty :: BST r a
empty = Nil

insert :: forall r a. MyOrd r a => a -> BST r a -> BST r a
insert a Nil = Bin Nil a Nil
insert a t@(Bin left key right) = case mycmp (Proxy :: Proxy r) a key of
   EQ -> t
   LT -> Bin (insert a left) key right
   GT -> Bin left key (insert a right)

fromList :: MyOrd r a => [a] -> BST r a
fromList xs = foldl' (flip insert) Nil xs

toAscList :: BST r a -> [a]
toAscList t = run t []
   where
     run Nil = id
     run (Bin left key right) = run left . (key :) . run right

Now we have it.

toAscList (fromList [3,1,4,15,9,2,6,5,38] :: BST () Int)
evaluates to
[1,2,3,4,5,6,9,15,38]

toAscList (fromList [3,1,4,15,9,2,6,5,38] :: BST Rev Int)
evaluates to
[38,15,9,6,5,4,3,2,1]

and both terms have the same type [Int]. The second term does not have 
to have type [Down Int].

Other applications include: Custom-making equivalence relations without 
calling them Eq; alternative interfaces to groupBy, sortBy, maximumBy, 
etc.; SML-style functorial programming; and liberating Complex from Ord.

I thank jadrian from IRC for proposing "named instance":

> so instead of "instance Num n => Monoid (Sum n) where" we'd write e.g. 
> "instance Sum of Num n => Monoid n where"   and use it as "Sum.mempty"

which stimulated me to think "oh we can emulate that by multiple 
parameter type class..."