Determining implementation of method based on available constraints

Question

Suppose I have to the following memoisation functions. (Ignore the fact that they are pure please.)

memoEq   :: Eq a       => (a -> b) -> a -> b
memoOrd  :: Ord a      => (a -> b) -> a -> b
memoHash :: Hashable a => (a -> b) -> a -> b

Now I want to have a construct that allows me to choose the 'best' of the above three memo functions. Something that essentially does the following:

memo f = case constraint_of_typevar_a_in f of
  Eq a       -> memoEq
  Ord a      -> memoOrd
  Hashable a -> memoHash

You can try this with type classes but you will get overlapping instances:

class Memo a where
  memo :: (a -> b) -> a -> b

instance Eq a => Memo a where
  memo = memoEq

instance Ord a => Memo a where
  memo = memoOrd

I've also attempted to use cast to retrieve the constraints. I realize that this would happen at run-time and as I was told in #haskell this is probably a bad idea. (I've omitted the cases for memoOrd and memoHash for sake of brevity.)

{-# LANGUAGE ImpredicativeTypes, ScopedTypeVariables #-}
module Main where

import Data.Typeable

memo :: forall a b. (Typeable a, Typeable b) => (a -> b) -> Maybe (a -> b)
memo f = 
    let eqf = cast f :: Eq a => Maybe (a -> b)
    in case eqf of
         Just eqf' -> Just    $ memoEq eqf'
         Nothing   -> Nothing

memoEq :: Eq a => (a -> b) -> a -> b
memoEq = undefined

memoOrd :: Ord a => (a -> b) -> a -> b
memoOrd = undefined

This code generates the following error message:

cast.hs:8:19:
Could not deduce (Eq a) arising from an expression type signature
from the context (Typeable a, Typeable b)
  bound by the type signature for
             memo :: (Typeable a, Typeable b) => (a -> b) -> Maybe (a -> b)
  at cast.hs:6:9-74
Possible fix:
  add (Eq a) to the context of
    the type signature for
      memo :: (Typeable a, Typeable b) => (a -> b) -> Maybe (a -> b)
In the expression: cast f :: Eq a => Maybe (a -> b)
In an equation for `eqf': eqf = cast f :: Eq a => Maybe (a -> b)
In the expression:
  let eqf = cast f :: Eq a => Maybe (a -> b)
  in
    case eqf of {
      Just eqf' -> Just $ memoEq eqf'
      Nothing -> Nothing }

Moving the Eq a constraint inside the Maybe gives an additional error that there is no Typeable1 constraint on Eq.

Could not deduce (Typeable1 Eq) arising from a use of `cast' from the context (Typeable a, Typeable b)

Is what I want to achieve possible, perhaps using Template Haskell? Or is it completely impossible and undesirable to be able to do this?

Answer 1

In GHC's implementation of type classes (and in general), it is not possible to look up class dictionaries at run time. The algorithm for generating dictionary code is integrated into the compiler's type inference engine, and there is no corresponding algorithm in any run-time code. As far as I know, there is no run-time database of all class instances, which you'd need in order to implement that algorithm. The design principle behind this is that types are not data, so a program cannot examine them.

Moreover, it isn't possible to choose the best memoization method at compile time because the type class system allows new instances to be defined. Because you can't prove that a type is not a member of Hashable—perhaps the instance definition is in a file that hasn't been compiled yet—you can't rule out the possibility that any given type should be memoized based on the Hashable class; the same thing goes for Eq and Ord.

I think the best solution is to manually choose how each type is memoized by writing Memo instances for each type constructor.