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

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产生一个额外的错误,即Typeable1Eq上没有约束.

无法从上下文中使用"强制转换"推断出(Typeable1 Eq)(Typeable a,Typeable b)

是我想要实现的,也许是使用Template Haskell？或者完全不可能也不可能做到这一点？

Answer 1

在GHC的类型类(以及一般)的实现中,不可能在运行时查找类字典.用于生成字典代码的算法被集成到编译器的类型推理引擎中,并且在任何运行时代码中都没有相应的算法.据我所知,没有所有类实例的运行时数据库,为了实现该算法,您需要它.这背后的设计原则是类型不是数据,因此程序无法检查它们.

此外,由于类型类系统允许定义新实例,因此无法在编译时选择最佳的memoization方法.因为您无法证明类型不是其成员 - Hashable实例定义可能尚未编译的文件中 - 您不能排除任何给定类型应基于Hashable类记忆的可能性; 同样的问题也发生在Eq和Ord.

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