Fabrikat Datentyp Art * -> * Das ist kein Functor

Question

Brent Yorgey die Typeclassopedia die folgende Übung gibt:

Geben Sie ein Beispiel für eine Art von Art * -> * die nicht eine Instanz Functor gemacht werden (ohne mit undefined).

Bitte sagen Sie mir, was bedeutet „kann keine Instanz Functor gemacht werden“.

Auch würde ich ein Beispiel zu schätzen wissen, aber vielleicht als Spoiler, so dass Sie, bitte, leitet mich auf die Antwort.

Answer 1

Lassen Sie uns über Varianzen sprechen.

Hier ist die Grundidee. Betrachten Sie den Typ A -> B. Ich möchte, dass Sie sich vorstellen, dass ein solcher Typ ähnlich ist wie "mit einem B" und auch "mit einem A".In der Tat, wenn Sie Ihre A zurückzahlen, erhalten Sie sofort Ihre B. Funktionen sind auf diese Art wie Escrow.

Der Begriff "Haben" und "Schuld" kann sich auf andere Typen erstrecken. Zum Beispiel ist die einfachste Behälter

newtype Box a = Box a 

verhält sich wie folgt: Wenn Sie „haben“ ein Box a dann „haben“ Sie auch eine a. Wir Arten betrachten, welche Art * -> * haben und „haben“ ihr Argument (kovarianten) functors zu sein, und wir können sie

instance Functor Box where fmap f (Box a) = Box (f a) 

zu Functor instanziiert Was passiert, wenn wir die Art von Prädikaten über eine Art betrachten, wie

newtype Pred a = Pred (a -> Bool) 

in diesem Fall, wenn wir eine Pred a haben, "schulden" wir eigentlich eine a. Dies ergibt sich aus der a auf der linken Seite des Pfeils (->). Wo fmap von Functor definiert wird, indem die Funktion in den Container übergeben wird und auf alle Orte angewendet wird, an denen wir unseren inneren Typ "haben", können wir nicht dasselbe für Pred a tun, da wir nicht "haben" und a s.

Stattdessen werden wir dies tun

class Contravariant f where 
    contramap :: (a -> b) -> (f b -> f a) 

Nun, da contramap ist wie ein "umgedreht" fmap? Es erlaubt uns, die Funktion auf die Orte anzuwenden, an denen wir eine b in Pred b "besitzen", um eine Pred a zu erhalten. Wir könnten contramap "Tauschhandel" nennen, weil es die Idee codiert, dass, wenn Sie wissen, wie man b s von a s bekommt, dann können Sie eine Schuld von b s in eine Schuld von a s verwandeln.

Mal sehen, wie es funktioniert

instance Contravariant Pred where 
    contramap f (Pred p) = Pred (\a -> p (f a)) 

wir unsere Handels laufen nur f mit bevor sie auf das Bestehen der Prädikatfunktion auf in. Wunderbar!

So jetzt haben wir kovariante und kontravariante Typen. Technisch sind diese als kovariante und kontravariante "Funktoren" bekannt. Ich werde auch sofort feststellen, dass fast immer ein kontravarianter Funktor nicht auch kovariant ist. Dies beantwortet also Ihre Frage: Es existiert eine Reihe kontravarianter Funktoren, die nicht in die Instanz Functor instanziiert werden können. Pred ist einer von ihnen.

Es gibt knifflige Typen, die sowohl kontravariante als auch kovariante Funktoren sind. Insbesondere die konstanten functors:

data Z a = Z -- phantom a! 

instance Functor  Z where fmap  _ Z = Z 
instance Contravariant Z where contramap _ Z = Z 

In der Tat können Sie im Wesentlichen, dass alles beweisen, die sowohl Contravariant und Functor einen Phantom Parameter haben.

isPhantom :: (Functor f, Contravariant f) => f a -> f b -- coerce?! 
isPhantom = contramap (const()) . fmap (const())  -- not really... 

Auf der anderen Seite, was mit einer Art geschieht, wie

-- from Data.Monoid 
newtype Endo a = Endo (a -> a) 

In Endo a wir beide verdanken und eine a erhalten.Bedeutet das, dass wir schuldenfrei sind? Nun, nein, es bedeutet nur, dass Endo sowohl kovariant als auch kontravariant sein will und hat keinen Phantomparameter. Das Ergebnis: Endo ist Invariante und kann weder Functor noch Contravariant instanziieren.

Answer 2

Ein Typ t von Art * -> * kann eine Instanz von Functor, wenn und nur gemacht werden, wenn es möglich ist, ein gesetzestreues Instanz der Functor Klasse für sie umzusetzen. Das heißt also, Sie die Functor Klasse zu implementieren, und Ihre fmap hat die Functor Gesetze zu befolgen:

fmap id x == x 
fmap f (fmap g x) == fmap (f . g) x 

Also im Grunde, dieses Problem zu lösen, müssen Sie irgendeine Art von Ihrer Wahl benennen und beweisen, dass es keine rechtmäßigen ist Implementierung von fmap dafür.

Beginnen wir mit einem nicht -Beispiel, um den Ton zu setzen. (->) :: * -> * -> * ist der Funktionstypkonstruktor, wie in den Funktionstypen String -> Int :: * zu sehen ist. In Haskell können Sie Typkonstruktoren teilweise anwenden, sodass Sie Typen wie (->) r :: * -> * haben können. Dieser Typ ist ein Functor:

instance Functor ((->) r) where 
    fmap f g = f . g 

Intuitiv die Functor Beispiel hier können Sie f :: a -> b auf den Rückgabewert einer Funktion g :: r -> a „vor“ anzuwenden (sozusagen) Sie g bis zu einem gewissen x :: r gelten. So zum Beispiel, wenn dies die Funktion, die die Länge des Arguments zurück:

length :: [a] -> Int 

... dann ist dies die Funktion, die die doppelte Länge des Arguments zurück:

twiceTheLength :: [a] -> Int 
twiceTheLength = fmap (*2) length 

Nützliche Tatsache : die Reader Monade ist nur ein newtype für (->):

newtype Reader r a = Reader { runReader :: r -> a } 

instance Functor (Reader r) where 
    fmap f (Reader g) = Reader (f . g) 

instance Applicative (Reader r) where 
    pure a = Reader (const a) 
    Reader f <*> Reader a = Reader $ \r -> f r (a r) 

instance Monad (Reader r) where 
    return = pure 
    Reader f >>= g = Reader $ \r -> runReader g (f r) r 

Nachdem wir nun, dass nicht-Beispiel aus dem Weg haben nicht, hier ist ein Typ, der kann gemacht werden, in eine Functor: die Reihenfolge der Parameter des Typs

type Redaer a r = Redaer { runRedaer :: r -> a } 

-- Not gonna work! 
instance Functor (Redaer a) where 
    fmap f (Redaer g) = ... 

Ja, alles, was ich tat, ist der Name rückwärts buchstabieren, und was noch wichtiger ist, drehen. Ich werde Sie versuchen zu verstehen, warum dieser Typ keine Instanz von Functor gemacht werden kann.