Turning A => M[B] into M[A => B]

by

In Practice

No, it can not be done, at least not in a meaningful way.

Consider this Haskell code

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

This takes n first, prints it (IO performed here), then reads a line from the user.

Assume we had an hypothetical transform :: (a -> IO b) -> IO (a -> b). Then as a mental experiment, consider:

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

The above has to do all the IO in advance, before knowing n, and then return a pure function. This can not be equivalent to the code above.

To stress the point, consider this nonsense code below:

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

Magically, action' should know in advance what the user is going to type next! A session would look as

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)

This requires a time machine, so it can not be done.

In Theory

No, it can not be done. The argument is similar to the one I gave to a similar question.

Assume by contradiction transform :: forall m a b. Monad m => (a -> m b) -> m (a -> b) exists.
Specialize m to the continuation monad ((_ -> r) -> r) (I omit the newtype wrapper).

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

Specialize r=a:

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

Apply:

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

By the Curry-Howard isomorphism, the following is an intuitionistic tautology

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

but this is Peirce’s Law, which is not provable in intuitionistic logic. Contradiction.

More Related Contents:

  1. How to convert A[B[C]] to B[A[C]] if A and B are monads?
  2. Why isn’t Validation a Monad?
  3. Scalaz Bind[Seq] typeclass
  4. What is a TypeTag and how do I use it?
  5. Enforce type difference
  6. What is a higher kinded type in Scala?
  7. What are type lambdas in Scala and what are their benefits?
  8. Method parameters validation in Scala, with for comprehension and monads
  9. Confused with the for-comprehension to flatMap/Map transformation
  10. Scala: How to define “generic” function parameters?
  11. What are some compelling use cases for dependent method types?
  12. Scala multiple type pattern matching
  13. Haskell: I/O and Returning From a Function
  14. Why is the Aux technique required for type-level computations?
  15. Update operations on a Scala Case Class
  16. Are HLists nothing more than a convoluted way of writing tuples?
  17. Static return type of Scala macros
  18. Using context bounds “negatively” to ensure type class instance is absent from scope
  19. Scala type programming resources
  20. Scalaz state monad examples
  21. forall in Scala
  22. What is a Singleton Type exactly?
  23. scala f-bounded types explanation
  24. Multiple parameter closure argument type not inferred
  25. What is the differences between Int and Integer in Scala?
  26. What is the advantage of using abstract classes instead of traits?
  27. Scala return statements in anonymous functions
  28. What is the difference between `##` and `hashCode`?
  29. Why can a Num act like a Fractional?
  30. Missing parameter type error by calling toSet?

Leave a Comment