Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Determining implementation of method based on available constraints

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?

like image 251
Alessandro Vermeulen Avatar asked May 29 '13 13:05

Alessandro Vermeulen


People also ask

What are implementation constraints?

Implementation constraints control placement and routing. They are not directly useful to XST, and are simply propagated and made available to the implementation tools. The constraints are written in the output NGC file. In addition, the object that an implementation constraint is attached to will be preserved.

What are the main implications of Theory of Constraints?

The Theory of Constraints focuses on identifying and removing constraints that limit throughput. Therefore, successful application tends to increase manufacturing capacity. Lean Manufacturing focuses on eliminating waste from the manufacturing process.

What are the 5 steps for managing constraints?

To further increase the throughput of the system, you must identify the new constraint, exploit the new constraint, subordinate everything else to the new constraint, and then elevate the new constraint. The process of on-going improvement is simply defined as the repetition of these five focusing steps.


1 Answers

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.

like image 163
Heatsink Avatar answered Oct 06 '22 17:10

Heatsink