基于可用约束确定方法的实现

Question

假设我有以下的回忆录功能。(请忽略它们是纯的这一事实。)

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

现在，我希望有一个结构，让我可以选择‘最好’以上三个备忘录功能。本质上做了以下工作的东西：

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

您可以尝试使用类型类，但会得到重叠的实例：

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

我还尝试使用cast检索约束。我意识到这种情况会在运行时发生，正如在#haskell中告诉我的那样，这可能是个坏主意。(为了简洁起见，我省略了memoOrd和memoHash的例子。)

{-# 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

此代码生成以下错误消息：

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 }

将Eq a约束移动到Maybe中会产生一个额外的错误，即在Eq上没有Typeable1约束。

无法从上下文(可键入a，可键入b)中推断(Typeable1公式)因使用“`cast”而产生的

我想要达到的目标是可能的吗，也许使用模板Haskell？还是完全不可能做到这一点，也是不可取的？

Answer 1

在GHC实现类型类(一般情况下)中，不可能在运行时查找类字典。将生成字典代码的算法集成到编译器的类型推理引擎中，在任何运行时代码中都没有相应的算法。据我所知，没有所有类实例的运行时数据库，您需要这些数据库来实现该算法。这背后的设计原则是类型不是数据，所以程序不能检查它们。

此外，不可能在编译时选择最佳的回忆法，因为类型类系统允许定义新的实例。由于无法证明某个类型不是Hashable-perhaps的成员，实例定义位于一个尚未编译的文件中--您不能排除任何给定类型都应该根据Hashable类进行回忆录的可能性；Eq和Ord也是如此。

我认为最好的解决方案是通过为每个类型构造函数编写Memo实例来手动选择每种类型的回忆录方式。