haskell - 根据可用约束确定方法的实现

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 中的约束给出一个额外的错误，即没有 Typeable1对等式的约束。

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

我想要实现的目标是否可能，也许是使用 Template Haskell？还是完全不可能和不希望能够做到这一点？

Answer 1

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

此外，不可能在编译时选择最佳的内存方法，因为类型类系统允许定义新实例。因为你不能证明一个类型不是 Hashable 的成员——也许实例定义在一个尚未编译的文件中——你不能排除任何给定类型都应该基于 Hashable 进行内存的可能性。类(class); Eq 也是如此和 Ord .

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