Comportamento della retromarcia >> = (==)

Question

Una funzione per determinare se una stringa è palindroma può essere implementato in modo applicativo pointfree via

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

Ed ecco una versione monadic

reverse >>= (==) 

Come funziona la versione modadica senza chiamate esplicite all'ID? Ho cercato di visualizzare la rappresentazione poinful usando pointful e riprendere la stessa funzione.

Answer 1

Questo funziona utilizzando il fatto che x -> y può essere considerato come una sorta di "lettore monade". Se dovessimo dire

type Reader r x = r -> x 

allora abbiamo un esempio di Monad (Reader r). Così possiamo vedere che

reverse :: [x] -> [x] 

è in realtà

reverse :: Reader [x] [x] 

Allo stesso modo,

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

può essere scritta come

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

Poi (>>=) unisce i due insieme.

Quindi ... Iniziamo con reverse, che è un'azione Reader che legge un elenco e restituisce un elenco. Usiamo quindi >>= per passarlo a ==, che è una funzione che prende una lista e restituisce un Reader [x] Bool.

In breve, l'elenco di input è duplicato dall'azione di Reader, che sostanzialmente prende un input e lo passa a ogni funzione nella catena. (Questo è ciò che il lettore monade è.)

spero che fatto qualche tipo di senso ... Ci sono voluti mi un po 'per capire!

Answer 2

Diamo uno sguardo ad istanza Monade per ((->) r):

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

e poi semplicemente inserire il tuo codice di monadica:

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

quale possiamo scrivere in un modo più familiare:

\r -> reverse r == r 

Answer 3

Per aggiungere ad altre risposte, ecco un altro punto di vista su questo. Prendiamo una definizione di bind con il fmap e join:

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

L'espressione è di tipo (==) <$> reverseEq a => [a] -> [a] -> Bool ed è equivalente a fmap (==) reverse.Ora, passiamo a join :: m (m a) -> m a e per l'istanza monad (->) r il tipo sarebbe ([a] -> [a] -> Bool) -> ([a] -> Bool). Cioè, join è esattamente la parte <*> id.

Answer 4

Penso che il modo più semplice per capire questo è guardando i tipi:

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

specializzato per l'istanza ((->) r):

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

Non è dato un a. L'unico modo per produrne uno è applicare la prima funzione r -> a allo r che ti è stata data. L'unico modo per produrre un b consiste nell'applicare la seconda funzione allo r e allo a appena prodotto. Questo significa che l'unica definizione possibile per questa funzione ^* è:

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

Collegando i nostri argomenti a, otteniamo:

reverse >>= (==) 

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

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

Parametricity è un potente strumento per ragionare sulle funzioni polimorfiche.

---

* diverso da fondo

Answer 5

Le altre risposte confermano che i due si comportano lo stesso, ma non spiegano dove il id realtà andato. In questa risposta, cercherò di farlo. La battuta finale è che, per Reader, abbiamo una curiosa equazione id -rimozione: id >>= return . f = f. (Una forma più bella di questa equazione è quella (id >>=) = (>>= id), insieme con le leggi della monade la bella forma implica la forma facilmente utilizzabile.) Per rendere la spiegazione un po 'più semplice, invece di cercare di convertire dalla forma applicativa alla forma monadica, lo farò basta dare per scontato che si ritiene la seguente equazione:

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

quindi partiremo da questa ultima linea, e terminerà alle reverse >>= (==). Lungo la strada, sarà fondamentale osservare che id è l'identità per (.) - che per caso è il fmap per la monade Reader. Andiamo:

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 >>= (==) 

Quindi qual è il significato di id >>= return . f = f? Bene, trattando le funzioni come "valori indicizzati", possiamo comprendere id come valore uguale al suo indice; e return come il valore che è lo stesso ovunque. Quindi id >>= return . f dice "guarda l'indice x, quindi, (ancora nell'indice x), restituisce il valore che ignora il suo indice e ha valore f x". Accade solo che l'indice che ignoriamo e il valore che abbiamo in mano a f coincidano, quindi potremmo anche ignorare tutto ciò che è indiretto e dire semplicemente "guarda l'indice x e applica f ad esso". Questo è il significato dell'equazione.