8

假设我必须使用以下记忆功能。（请忽略它们是纯净的事实。）

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

无法从上下文（Typeable a，Typeable b）中推断出（Typeable1 Eq）因使用“cast”而产生

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

4

1 回答 1

12

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

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

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

于 2013-05-29T14:44:33.087 回答