Es wird behauptet, dass newtype T a = T (a -> Int) ein Typkonstruktor ist, der kein Funktor ist (aber ein kontravarianter Funktor ist). Wie das? Oder was ist der kontravariante Funktor (woher nehme ich an, dass es offensichtlich ist, warum dies nicht zu einem normalen Funktor gemacht werden kann)?Zeigen, dass `newtype T a = T (a -> Int)` ist ein Typkonstruktor, der kein Functor ist
Bei
newtype T a = T (a -> Int)
wollen wir versuchen, die Contravariant Instanz für diesen Datentyp zu bauen.
Hier ist die typeclass in Frage:
class Contravariant f where
contramap :: (a -> b) -> f b -> f a
Grundsätzlich contramap ist verwandt mit fmap, sondern eine Funktion der Aufhebung a -> b-f a -> f b, hebt es auf f b -> f a.
Lasst uns beginnen, um die Instanz zu schreiben ...
instance Contravariant T where
contramap g (T f) = ?
Bevor wir in der ? füllen, lassen Sie uns darüber nachdenken, was die Arten von g und f sind:
g :: a -> b
f :: b -> Int
Und für Klarheit, wir könnte auch erwähnen, dass
f a ~ T (a -> Int)
f b ~ T (b -> Int)
So können wir in der ? füllen Sie wie folgt vor:
instance Contravariant T where
contramap g (T f) = T (f . g)
Super pedantisch zu sein, Sie g als aToB umbenennen könnte, und f als bToInt.
instance Contravariant T where
contramap aToB (T bToInt) = T (bToInt . aToB)
Der Grund, warum Sie eine Contravariant Instanz für T a schreiben kann, läuft darauf hinaus auf die Tatsache, dass a in T (a -> Int) in kontra Position befindet. Der beste Weg, sich davon zu überzeugen, dass T a kein Functor ist, ist zu versuchen (und scheitern), die Functor Instanz selbst zu schreiben.
Angenommen, T ist ein Funktor. Dann haben wir
fmap :: (a -> b) -> T a -> T b
Jetzt versuchen wir es zu implementieren.
instance Functor T where
fmap f (T g) = T $ \x -> _y
Offensichtlich beginnen wir mit so etwas, und kombinieren Sie die Werte f, g und x irgendwie einen Wert für y zu berechnen, die von der richtigen Art ist. Wie können wir das machen? Nun, beachte, dass ich es _y genannt habe, was GHC sagt, dass ich Hilfe brauche, um herauszufinden, was ich dort hinlege. Was sagt GHC?
<interactive>:7:28: error:
• Found hole: _y :: Int
Or perhaps ‘_y’ is mis-spelled, or not in scope
• In the expression: _y
In the second argument of ‘($)’, namely ‘\ x -> _y’
In the expression: T $ \ x -> _y
• Relevant bindings include
x :: b (bound at <interactive>:7:23)
g :: a -> Int (bound at <interactive>:7:13)
f :: a -> b (bound at <interactive>:7:8)
fmap :: (a -> b) -> T a -> T b (bound at <interactive>:7:3)
So jetzt sind wir klar über die Arten von allem relevanten, richtig? Wir brauchen eine Int irgendwie zurückzukehren, und was wir haben es sind aus zu bauen:
x :: b
g :: a -> Int
f :: a -> b
Na ja, okay, das einzige, was wir haben, dass möglicherweise erstellen eine Int ist g, so lassen wir das ausfüllen, g ‚s Argument Aussparen für mehr Hilfe GHC zu fragen:
instance Functor T where
fmap f (T g) = T $ \x -> g _y
<interactive>:7:31: error:
• Found hole: _y :: a
Where: ‘a’ is a rigid type variable bound by
the type signature for:
fmap :: forall a b. (a -> b) -> T a -> T b
at <interactive>:7:3
Or perhaps ‘_y’ is mis-spelled, or not in scope
• In the first argument of ‘g’, namely ‘(_y)’
In the expression: g (_y)
In the second argument of ‘($)’, namely ‘\ x -> g (_y)’
• Relevant bindings include
x :: b (bound at <interactive>:7:23)
g :: a -> Int (bound at <interactive>:7:13)
f :: a -> b (bound at <interactive>:7:8)
fmap :: (a -> b) -> T a -> T b (bound at <interactive>:7:3)
okay, wir dies sie vorausgesagt haben könnten: g nennen, müssen wir einen Wert vom Typ a von irgendwo. Aber wir haben keine Werte des Typs a im Bereich, und wir haben auch keine Funktionen, die einen Wert vom Typ a entweder zurückgeben! Wir stecken fest: Es ist unmöglich, einen Wert des Typs zu produzieren, den wir jetzt wollen, obwohl wir bei jedem Schritt das einzig mögliche getan haben: Es gibt nichts, was wir sichern und anders ausprobieren könnten.
Warum ist das passiert? Denn wenn ich dir eine Funktion vom Typ a -> Int gebe und sage "aber nebenbei, hier ist eine Funktion von a -> b, gib mir bitte eine Funktion von b -> Int statt", kannst du eigentlich die Funktion der Funktion a -> b nutzen, weil niemand gibt dir überhaupt a s, um es anzurufen! Wenn ich Ihnen statt dessen eine Funktion von b -> a gegeben hätte, wäre das sehr hilfreich, oder? Sie könnten eine Funktion von b -> Int dann erzeugen, indem Sie zuerst die b -> a Funktion aufrufen, um eine a zu erhalten, und dann die ursprüngliche a -> Int Funktion aufrufen, um die gewünschte Int herauszuholen.
Und das ist, was ein kontravarianter Funktor ist: Wir kehren den Pfeil in der Funktion fmap um, so kann es fmap über Dinge, die Sie "brauchen" (Funktionsargumente) statt Dinge, die Sie haben (konkrete Werte, zurück Werte von Funktionen usw.).
Abgesehen: Ich behauptete früher, dass wir bei jedem Schritt „die einzig mögliche Sache“ getan hatten, was ein bisschen ein fib war. Wir können kein Int aus f, g und x bauen, aber natürlich können wir alle Arten von Zahlen aus der Luft machen.Wir wissen nichts über den Typ b, so dass wir keine Int bekommen können, die von ihm in irgendeiner Weise abgeleitet ist, aber wir könnten einfach sagen "lass uns immer Null zurückgeben", und das erfüllt technisch die Typüberprüfung:
instance Functor T where
fmap f (T g) = T $ const 0
Offensichtlich sieht das ziemlich falsch aus, da es scheint, f und g sollte ziemlich wichtig sein und wir ignorieren sie! Aber es tippt, also sind wir okay, oder?
Nein, verletzt dies eine der Functor Gesetze:
fmap id = id
Wir dies leicht genug beweisen können:
fmap id (T $ const 5) = (T $ const 0) /= (T $ const 5)
Und jetzt haben wir wirklich haben alles versucht: der einzige Weg, wir haben einen Int zu bauen, ohne unseren b Typ überhaupt zu benutzen, ist es aus nichts zu machen, und alle solche Verwendungen werden isomorph zu const sein, was gegen die Functor Gesetze verstößt.
Hier ist noch ein bisschen Perspektive. Wie liminisch zeigte, ist TContravariant.Was können wir über Typen sagen, die sowohl kovariant als auch kontravariant sind?
import Data.Void
change1, change1', change2 :: (Functor f, Contravariant f) => f a -> f b
change1 = contramap (const()) . fmap (const())
change1' = (() >$) . (() <$)
change2 = fmap absurd . contramap absurd
Die ersten beiden Implementierungen sind im Grunde die gleichen (change1' eine Optimierung der change1 ist); jeder von ihnen verwendet die Tatsache, dass () ein "Terminal-Objekt" von Hask ist. change2 nutzt stattdessen die Tatsache, dass Void ein "anfängliches Objekt" ist.
Jede dieser Funktionen ersetzt die alle a s in f a mit b s ohne a haupt über irgendetwas zu wissen, b, oder die Beziehung zwischen ihnen, alles andere das gleiche bleibt. Es sollte wohl klar sein, dass dies f a nicht wirklich von a abhängt. Das heißt, f 's Parameter muss Phantom sein. Das ist nicht der Fall für T, so kann es auch nicht kovariant sein.