Funzione Monad di conseguenza in Haskell

Question

Sto riscontrando qualche problema nella progettazione della funzione di controffunzione della funzione sequence di Haskell, che Hoogle mi dice che non esiste ancora. Questo è come si comporta:

ghci> sequence [Just 7, Just 8, Just 9] 
Just [7,8,9] 
ghci> sequence [getLine, getLine, getLine] 
hey 
there 
stack exchange 
["hey","there","stack exchange"] :: IO [String] 

Il mio problema sta facendo una funzione come questa:

unsequence :: (Monad m) => m [a] -> [m a] 

modo che si comporti in questo modo:

ghci> unsequence (Just [7, 8, 9]) 
[Just 7, Just 8, Just 9] 
ghci> sequence getLine 
hey 
['h','e','y'] :: [IO Char] --(This would actually cause an error, but hey-ho.) 

io in realtà non so se è possibile, perché a un certo punto sarei scappato dalla monade, ma ho fatto un salto, anche se non so come impostare un breakpoint per questa funzione ricorsiva:

unsequence m = (m >>= return . head) : unsequence (m >>= return . tail) 

mi rendo conto che ho bisogno di un punto di interruzione quando il m qui è uguale a return [], ma non tutte le monadi hanno Eq casi, quindi come posso fare questo? È possibile? Se è così, perché e perché no? Per favore dimmelo

Answer 1

Non è infatti possibile creare una funzione unsequence utilizzando solo le sole. Il motivo è:

1. È possibile creare in modo semplice e sicuro una struttura monadica da un valore utilizzando return.
2. Tuttavia, non è sicuro rimuovere un valore da una struttura monadica. Ad esempio non è possibile rimuovere un elemento da una lista vuota (ad esempio una funzione del tipo [a] -> a non è sicura).
3. Quindi abbiamo una funzione speciale (ad esempio >>=) che rimuove in modo sicuro un valore da una struttura monadica (se esistente), lo elabora e restituisce un'altra struttura monadica sicura.

Quindi è sicuro creare una struttura monadica da un valore. Tuttavia non è sicuro rimuovere un valore da una struttura monadica.

Supponiamo di avere una funzione extract :: Monad m => m a -> a che potrebbe “ in modo sicuro ” rimuovere un valore da una struttura monadica. Potremmo quindi implementare unsequence come segue:

unsequence :: Monad m => m [a] -> [m a] 
unsequence = map return . extract 

Tuttavia, non c'è modo sicuro per estrarre un valore da una struttura monadica. Quindi unsequence [] e unsequence Nothing restituiranno undefined.

È tuttavia possibile creare una funzione unsequence per strutture che sono sia monadiche che comonadiche. Un Comonad è definito come segue:

class Functor w => Comonad w where 
    extract :: w a -> a 
    duplicate :: w a -> w (w a) 
    extend :: (w a -> b) -> w a -> w b 

    duplicate = extend id 
    extend f = fmap f . duplicate 

Una struttura comonadic è l'opposto di una struttura monadico. In particolare:

1. È possibile estrarre in modo sicuro un valore da una struttura comonadica.
2. Tuttavia non è possibile creare in modo sicuro una nuova struttura comonadica da un valore, motivo per cui la funzione duplicate crea in modo sicuro una nuova struttura comonadica da un valore.

ricordare che la definizione di unsequence richiesto sia return e extract? Non è possibile creare in modo sicuro una nuova struttura comonadica da un valore (ad esempio le strutture comonadiche non hanno return). Quindi la funzione unsequence è definito come segue:

unsequence :: (Comonad m, Monad m) => m [a] -> [m a] 
unsequence = map return . extract 

interessante notare sequence lavori su strutture semplicemente monadici. Quindi attraverso l'intuizione si potrebbe supporre che unsequence funzioni su strutture semplicemente comonadiche. Tuttavia non è così perché è necessario prima estrarre la lista dalla struttura comonadica e quindi inserire ciascun elemento della lista in una struttura monadica.

La versione generale della funzione unsequence converte una struttura lista comonadic ad una lista di strutture monadici:

unsequence :: (Comonad w, Monad m) => w [a] -> [m a] 
unsequence = map return . extract 

D'altra parte la funzione sequence lavora su strutture semplicemente monadici perché si sta appena piegare la lista delle strutture monadici in una struttura lista monadica concatenando tutte le monadi:

sequence :: Monad m => [m a] -> m [a] 
sequence = foldr cons (return []) 
    where cons mx mxs = do 
     x <- mx 
     xs <- mxs 
     return $ x:xs 

Speranza che aiuta.

Answer 2

Non è possibile avere un unsequence :: (Monad m) => m [a] -> [m a]. Il problema si trova nelle liste: non si può essere sicuri di quanto possano essere elementi con una lista e questo complica qualsiasi ragionevole definizione di unsequence.

È interessante notare che, se si dovesse assolutamente, al 100% sicuro che l'elenco all'interno della monade è infinita, si potrebbe scrivere qualcosa di simile a:

unsequenceInfinite :: (Monad m) => m [a] -> [m a] 
unsequenceInfinite x = fmap head x : unsequenceInfinite (fmap tail x) 

E che avrebbe funzionato!

Immaginate anche di avere un funtore Pair in giro. Possiamo scrivere unsequencePair come

unsequencePair :: (Monad m) => m (Pair a) -> Pair (m a) 
unsequencePair x = Pair (fmap firstPairElement x) (fmap secondPairElement x) 

In generale, si scopre che si può solo definire unsequence per funtori con la proprietà che si può sempre "zip" insieme due valori senza perdere informazioni. Gli elenchi infiniti (in Haskell, un tipo possibile per loro è Cofree Identity) sono un esempio. Il functor Pair è un altro. Ma non elenchi convenzionali, o funtori come Maybe o Either.

Nel pacchetto distributive, esiste una classe di caratteri denominata Distributive che incapsula questa proprietà. Il tuo unsequence si chiama distribute lì.