Определение реализации метода на основе доступных ограничений

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 ограничение по формуле

Не удалось вывести (Typeable1 Eq), возникающее из использования `cast'из контекста (Typeable a, Typeable b)

Возможно ли то, чего я хочу достичь, возможно, используя Template Haskell? Или это абсолютно невозможно и нежелательно иметь возможность сделать это?

Answer 1

В GHC-реализации классов типов (и вообще), невозможно найти словари классов во время выполнения. Алгоритм генерации кода словаря интегрирован в механизм вывода типов компилятора, и в любом коде выполнения нет соответствующего алгоритма. Насколько я знаю, во время выполнения не существует базы данных всех экземпляров классов, которая понадобится вам для реализации этого алгоритма. Принцип проектирования заключается в том, что типы не являются данными, поэтому программа не может их проверить.

Более того, невозможно выбрать лучший метод запоминания во время компиляции, потому что система классов типов позволяет определять новые экземпляры. Потому что вы не можете доказать, что тип не является членом Hashable- возможно, определение экземпляра находится в файле, который еще не был скомпилирован - вы не можете исключить возможность того, что любой данный тип должен быть запомнен на основе Hashable учебный класс; то же самое относится и к Eq а также Ord,

Я думаю, что лучшее решение - вручную выбрать способ запоминания каждого типа, написав Memo экземпляры для каждого конструктора типа.