2013-05-29 14 views
8

Angenommen, ich habe folgende Memo-Funktionen. (Ignorieren Sie die Tatsache, dass sie rein sind, bitte.)Ermittlung der Implementierung der Methode basierend auf verfügbaren Einschränkungen

memoEq :: Eq a  => (a -> b) -> a -> b 
memoOrd :: Ord a  => (a -> b) -> a -> b 
memoHash :: Hashable a => (a -> b) -> a -> b 

Jetzt möchte ich ein Konstrukt haben, die mir die ‚besten‘ der drei oben genannten Memo-Funktionen auswählen können. Etwas, das im Wesentlichen macht folgendes:

memo f = case constraint_of_typevar_a_in f of 
    Eq a  -> memoEq 
    Ord a  -> memoOrd 
    Hashable a -> memoHash 

Sie können versuchen, diese mit Typ-Klassen, aber Sie werden überlappende Instanzen erhalten:

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 

Ich habe auch die Einschränkungen zu verwenden cast abzurufen versucht. Mir ist klar, dass dies zur Laufzeit passieren würde und wie mir in #haskell gesagt wurde, ist das wahrscheinlich eine schlechte Idee. (Ich habe die Fälle für memoOrd und memoHash der Kürze halber weggelassen.)

{-# 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 

Dieser Code erzeugt die folgende Fehlermeldung:

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 } 

Verschieben der Eq a Einschränkung innerhalb der Maybe einen zusätzlichen Fehler gibt dass es keine Typeable1 Einschränkung auf Gl.

kann ableiten nicht (Typeable1 Eq) von einer Verwendung von `werfen‘ aus dem Kontext ergeben (typisierbarem a, typisierbarer b)

Ist das, was ich möglich erreichen will, vielleicht Template Haskell mit ? Oder ist es völlig unmöglich und unerwünscht, dies tun zu können?

+1

Was passiert, wenn 'memoEqOrd'? erlaubst du es nicht? – josejuan

+0

@josejuan: Das wäre kein Problem, ich würde entweder memoOrd oder memoEq auswählen. Angenommen, es gibt eine Reihenfolge in den Memo-Funktionen, aber die gerade nicht wichtig ist, fühle ich jetzt. –

Antwort

12

In der GHC-Implementierung von Typklassen (und im Allgemeinen) ist es nicht möglich, Klassenwörterbücher zur Laufzeit nachzuschlagen. Der Algorithmus zum Erzeugen eines Wörterbuchcodes ist in die Typ-Inferenzmaschine des Compilers integriert, und es gibt keinen entsprechenden Algorithmus in irgendeinem Laufzeitcode. Soweit ich weiß, gibt es keine Laufzeitdatenbank aller Klasseninstanzen, die Sie benötigen, um diesen Algorithmus zu implementieren. Das Design-Prinzip dahinter ist, dass Typen keine Daten sind, also kann ein Programm sie nicht untersuchen.

Darüber hinaus ist es nicht möglich, die beste Memo-Methode zum Zeitpunkt der Kompilierung auszuwählen, da das Typklassensystem die Definition neuer Instanzen zulässt. Da Sie nicht beweisen können, dass ein Typ nicht ein Mitglied von Hashable ist - vielleicht ist die Instanzdefinition in einer Datei, die noch nicht kompiliert wurde - können Sie die Möglichkeit nicht ausschließen, dass ein beliebiger Typ memoisiert werden sollte auf der Hashable Klasse; das gleiche gilt für Eq und Ord.

Ich denke, die beste Lösung ist manuell zu wählen, wie jeder Typ Memo ist, indem Memo Instanzen für jeden Typ Konstruktor schreiben.

+0

Klare und präzise Antwort, auch über die Laufzeit und die Arten Bit. –

Verwandte Themen