Verhalten von Reverse >> = (==)

Question

Eine Funktion zur Bestimmung, ob ein String ein Palindrom ist über

pal1 = (==) <$> reverse <*> id 

in einer pointfree applicative Weise implementiert werden, und hier ist eine monadische Version

reverse >>= (==) 

Wie funktioniert die modadische Version ohne expliziten Aufruf von id? Ich habe versucht, die poinful Darstellung mit Pointful zu sehen und die gleiche Funktion zurück zu bekommen.

Answer 1

Dies funktioniert mit der Tatsache, dass x -> y kann als eine Art "Reader Monade" angesehen werden. Wenn wir

type Reader r x = r -> x 

sagen würde, dann haben wir eine Instanz von Monad (Reader r). So können wir sehen, dass

reverse :: [x] -> [x] 

tatsächlich

reverse :: Reader [x] [x] 

Ähnlich ist

(==) :: [x] -> [x] -> Bool 

als

geschrieben werden

(==) :: [x] -> Reader [x] Bool 

Dann (>>=) verbindet die beiden zusammen.

So ... Wir beginnen mit reverse, die eine Reader Aktion ist, die eine Liste liest und eine Liste zurückgibt. Wir verwenden dann >>=, um das an == zu übergeben, was eine Funktion ist, die eine Liste annimmt und eine Reader [x] Bool zurückgibt.

Kurz gesagt, die Eingabeliste wird durch die Aktion Reader dupliziert, die grundsätzlich eine Eingabe nimmt und sie an jede Funktion in der Kette weitergibt. (Das ist, was der Leser Monade ist.)

Ich hoffe, dass irgendeine Art von Sinn gemacht ... Es hat mich eine Weile, um herauszufinden!

Answer 2

Schauen wir uns die Monade Instanz für ((->) r) einen Blick:

instance Monad ((->) r) where 
    return = const 
    f >>= k = \ r -> k (f r) r 

und dann einfach in Ihrem monadischen Code füllen:

reverse >>= (==) = \r -> (==) (reverse r) r 

, die wir in einer vertrauteren Art und Weise schreiben:

\r -> reverse r == r 

Answer 3

Um zu anderen Antworten hinzuzufügen, hier ist ein weiterer POV zu diesem Thema. Lassen Sie uns eine Definition binden nehmen über fmap und join:

m >>= act = join (fmap act m) 

Der Ausdruck hat (==) <$> reverseEq a => [a] -> [a] -> Bool Typ und entspricht fmap (==) reverse.Jetzt übergeben wir es an join :: m (m a) -> m a und für (->) r Monad-Instanz wäre der Typ ([a] -> [a] -> Bool) -> ([a] -> Bool). Das heißt, Join ist genau <*> id Teil.

Answer 4

Ich denke, der einfachste Weg, dies zu verstehen, ist die Art von Suche:

(>>=) :: Monad m => m a -> (a -> m b) -> m b 

spezialisiert auf das ((->) r) Beispiel:

(>>=) :: (r -> a) -> (a -> r -> b) -> r -> b 

Sie sind ein a nicht gegeben. Die einzige Möglichkeit, einen zu erzeugen, besteht darin, die erste Funktion auf die r anzuwenden, die Sie erhalten. Die einzige Möglichkeit, ein b zu erzeugen, ist, die zweite Funktion auf die r und die a anzuwenden, die Sie gerade produziert haben. Das bedeutet, die einzig mögliche Definition für diese Funktion ^* ist:

f >>= g = \a -> g (f a) a 

unsere Argumente in Anstecken, erhalten wir:

reverse >>= (==) 

-- definition of (>>=) 
= \a -> (==) (reverse a) a 

-- prefix to infix 
= \a -> reverse a == a 

Parametrizität ist ein leistungsfähiges Werkzeug für die Argumentation über polymorphe Funktionen.

---

* andere als unten

Answer 5

Die anderen Antworten bestätigen, dass die beiden gleich verhalten, aber nicht erklären, wo die id tatsächlich ging. In dieser Antwort werde ich versuchen, dies zu tun. Die Pointe ist, dass wir für den Leser eine seltsame id -Entfernungsgleichung haben: id >>= return . f = f. (Eine schönere Form dieser Gleichung ist die (id >>=) = (>>= id); zusammen mit den Monadengesetzen impliziert die schöne Form die leicht verwendbare Form.) Um die Erklärung etwas einfacher zu machen, anstatt zu versuchen, von der anwendbaren Form in die monadische Form zu konvertieren, werde ich es tun nur es für selbstverständlich, dass Sie die folgende Gleichung glauben:

(==) <$> reverse <*> id 
= { too annoying to do carefully } 
reverse >>= \xs -> id >>= \ys -> return ((==) xs ys) 

So werden wir von der letzten Zeile beginnen und bei reverse >>= (==) beenden. Auf dem Weg wird es wichtig sein zu beobachten, dass id ist die Identität für (.) - die gerade so ist fmap für den Reader Monad. Hier gehen wir:

reverse >>= \xs -> id >>= \ys -> return ((==) xs ys) 
= { monad law } 
reverse >>= \xs -> fmap ((==) xs) id 
= { definition of fmap for Reader } 
reverse >>= \xs -> (.) ((==) xs) id 
= { id is the identity of fmap } 
reverse >>= \xs -> (==) xs 
= { eta reduction } 
reverse >>= (==) 

Also was bedeutet id >>= return . f = f? Wenn wir Funktionen als "indizierte Werte" behandeln, können wir id als den Wert verstehen, der seinem Index entspricht; und return als der Wert, der überall gleich ist. So id >>= return . f sagt "Blick auf Index x; dann, (immer noch bei Index x), geben Sie den Wert, der seinen Index ignoriert und hat den Wert f x". Es passiert einfach, dass der Index, den wir ignorieren, und der Wert, den wir an f übergeben, zusammenpasst - also können wir die Indirektion einfach überspringen und einfach sagen: "Schauen Sie sich den Index x an und wenden Sie f darauf an". Dies ist die Bedeutung der Gleichung.