Tornitura A => M [B] in M ​​[A => B]

Question

Per una monade M, È possibile attivare A => M[B] in M[A => B]?

Ho provato a seguire i tipi senza alcun risultato, il che mi fa pensare che non sia possibile, ma ho pensato di chiedere comunque. Inoltre, la ricerca di Hoogle per a -> m b -> m (a -> b) non ha restituito nulla, quindi non sto dando molto sfogo.

Answer 1

In pratica

No, non si può fare, almeno non in modo significativo.

Considerate questo codice Haskell

action :: Int -> IO String 
action n = print n >> getLine 

Questo richiede n prima, lo stampa (IO eseguita qui), poi legge una riga da parte dell'utente.

Supponiamo di avere un ipotetico transform :: (a -> IO b) -> IO (a -> b). Poi, come un esperimento mentale, prendere in considerazione:

action' :: IO (Int -> String) 
action' = transform action 

È possibile che questo ha a che fare tutto il IO in anticipo, prima di conoscere n, e poi restituire una pura funzione. Questo non può essere equivalente al codice sopra.

Per sottolineare il punto, si consideri questo codice assurdità di seguito:

test :: IO() 
test = do f <- action' 
      putStr "enter n" 
      n <- readLn 
      putStrLn (f n) 

Magicamente, action' dovrebbe sapere in anticipo ciò che l'utente sta per digitare prossima! Una sessione potrebbe apparire come

42  (printed by action') 
hello (typed by the user when getLine runs) 
enter n 
42  (typed by the user when readLn runs) 
hello (printed by test) 

Ciò richiede una macchina del tempo, quindi non può essere eseguita.

in teoria

No, non può essere fatto. L'argomento è simile a the one I gave to a similar question.

Presuppone per contraddittorio transform :: forall m a b. Monad m => (a -> m b) -> m (a -> b) esistente. Specialize m alla continuazione monad ((_ -> r) -> r) (ometto il wrapper newtype).

transform :: forall a b r. (a -> (b -> r) -> r) -> ((a -> b) -> r) -> r 

Specializzarsi r=a:

transform :: forall a b. (a -> (b -> a) -> a) -> ((a -> b) -> a) -> a 

Applicare:

transform const :: forall a b. ((a -> b) -> a) -> a 

Con l'isomorfismo di Curry-Howard, il seguente è una tautologia intuizionistico

((A -> B) -> A) -> A 

ma questo è Peirce ' s Legge, che non è dimostrabile nella logica intuizionista. Contraddizione.

Answer 2

No.

Per esempio, Option è una monade, ma la funzione (A => Option[B]) => Option[A => B] non ha alcuna applicazione significativa:

def transform[A, B](a: A => Option[B]): Option[A => B] = ??? 

Cosa mettere al posto di ???? Some? Some di cosa poi? O None?

Answer 3

Le altre risposte hanno ben illustrato che in generale non è possibile implementare una funzione da a -> m b a m (a -> b) per qualsiasi monad m. Tuttavia, ci sono monadi specifici in cui è abbastanza possibile implementare questa funzione. Un esempio è la monade lettore:

data Reader r a = R { unR :: r -> a } 

commute :: (a -> Reader r b) -> Reader r (a -> b) 
commute f = R $ \r a -> unR (f a) r