Haskell polymorphe Funktionsauswertung Fehler

Question

Der folgende Code nicht kompiliert:

foo :: Num a => (a -> a) -> Either Integer Double -> Either Integer Double 
foo f x = case x of 
    Left i -> Left $ f i 
    Right d -> Right $ f 

und gibt die folgenden Fehler:

Couldn't match type `Integer' with `Double' 
Expected type: Either Integer Double 
Actual type: Either Integer a 
In the expression: Right $ f d 
In a case alternative: Right d -> Right $ f d 

Dies ist eine Follow-up-Frage zu this question, das Problem durch gelöst mit RankNTypes:

(forall a. Num a => a -> a) 

Aber die Antwort hat nichts gesagt. Ich möchte wissen:

• Was ist die Ursache dieses Fehlers? Das Eventual-Ergebnis wäre nur einer der Case-Zweig, f würde nicht auf zwei Typen gleichzeitig eingegeben werden, sollte der Typ f überprüft werden, solange f :: Num a => (a -> a), entweder Integer -> Integer oder Double -> Double sollte Arbeit, könnte jemand erläutern, warum dies einen Fehler verursacht?

• Gibt es eine andere Möglichkeit, den Fehler zu beheben? Warum würde RankNTypes den Fehler beheben? Dies trifft mich wie der Monomorphie-Restriktionsfehler, den ich neulich bekommen habe, aber die Aktivierung hilft mir nicht, das zu beheben, und die explizite Typ-Annotation funktioniert auch nicht.

Answer 1

Die Ursache ist, dass mit Ihrer ursprünglichen Definition a zu allgemein ist. Bedenken Sie:

foo :: Num a => (a -> a) -> Either Integer Double -> Either Integer Double 
foo f x = case x of 
    Left i -> Left $ f i 

An diesem Punkt ist die Art Kontrolleur kommt in Schwierigkeiten, weil die Art der Left $ f iEither Integer Double sein muss, daher der Ausdruck f i muss Integer sein. Aber Sie haben gesagt, dass der Aufrufer irgendeine Funktion übergeben kann, die einen numerischen Typ auf sich selbst abbildet. Zum Beispiel erlaubt Ihre Typ-Signatur eine Double -> Double Funktion zu übergeben. Natürlich kann eine solche Funktion niemals zu Integer führen, daher ist die Anwendung von f hier nicht gut typisiert.

OTOH, wenn Sie die Lösung mit höherrangigen Typen verwenden, können Sie keine Funktion übergeben, die für bestimmte Typen funktioniert - nur Funktionen, die unter alle numerischen Typen funktionieren. Zum Beispiel könnten Sie negate, aber nicht ((1::Integer)+) übergeben. Dies ist absolut sinnvoll, da Sie in einem anderen Fall alternativ auch die gleiche Funktion auf einen Double Wert anwenden.

Also, um Ihre zweite Frage zu beantworten, ist die höherrangige Typ Lösung die richtige, Ihren Code gegeben. Sie können natürlich nur Funktionen wie negate weitergeben, wenn Sie es auf eine Integer und eine Double anwenden möchten.

Fazit: Mit

f :: (a -> a) -> b 

Sie Funktionen wie id passieren könnte tail, reverse, ((1::Int)+). Mit

f :: (forall a. a -> a) -> b 

konnte man nur Funktionen mit übergeben, die Art Signatur exaktforall a. a->a (Modulo Typ Variablenumbenennung) wie id, aber keiner der anderen oben erwähnt.

Answer 2

Grundlegend ist dies ein Scoping-Problem. Lassen Sie uns die folgende Art Entwürfe vergleichen:

foo1 :: Num a => (a -> a) -> ...

foo2 :: (. Forall eine Num a => a -> a) -> ...

In der ersten Deklaration möchte der Compiler einen Typ a haben, der eine Instanz von Num und eine Funktion des Typs a -> a für diesen bestimmten Typ ist. Speziell eine Funktion, die nur mit Integer funktioniert, würde hier passen. Natürlich passt eine solche Funktion nicht zu Ihrer Aufgabe, daher lehnt der Compiler Ihre Implementierung zu Ihrer gegebenen Typsignatur zu Recht ab. Auf der anderen Seite besagt die Signatur des zweiten Typs, dass Sie eine Funktion vom Typ a -> a haben möchten, die für alle Instanzen von Num funktioniert. Dieser Typ ist im Vergleich zu ersteren deutlich eingeschränkt.

foo :: (a -> a) -> (b -> b) -> Either a b -> Either a b 
foo f g = either (Left . f) (Right . g) 

Answer 3

Es ist eine Frage des Umfangs, wirklich:

Als Abhilfe können Sie die Funktion benötigen könnten zweimal gegeben werden.

Im Original haben Sie eine neue Typvariable für jede Instanz von foo.

foo :: forall a. Num a => (a -> a) -> Either Integer Double -> Either Integer Double 

a müssen für den gesamten Körper jeder Instanziierung foo werden, und nur eine Instanz Num beteiligt ist. Während Sie in der polymorphen Rang-2-Version eine neue Typvariable für jede Instanziierung des f-Parameters haben.

foo :: (forall a. Num a => a -> a) -> Either Integer Double -> Either Integer Double 

Und Sie sprechen so viele Num Instanzen wie es instantiations sind.