确定实施

Question

假设我有以下memoisation功能。 （忽视的事实是，他们是纯粹的请。）

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约束。

从上下文中使用的'投” （分型一，分型B）

出现无法推断（Typeable1当量）我要实现的可能，可能使用模板哈斯克尔什么？或者是完全不可能和不希望能够做到这一点？

Answer 1

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

而且，无法选择在编译时最好记忆化方法，因为型类系统允许定义新的实例。因为你不能证明一个类型是不的Hashable成员-perhaps实例定义是在尚未编制尚未你不能排除任何给定类型应根据被memoized的可能性文件在Hashable课上; Eq和Ord也是一样的。

我认为最好的办法是手动选择每类是通过写Memo情况下，每种类型的构造memoized。