Transforming mostly-monadic code to mostly-applicative code

transforming.md

Transforming mostly-monadic code to mostly-applicative code

There’s an Applicative do-notation proposal whose stage 2 matches this, except that it operates within do desugaring while this operates on raw >>=/return applications. Reddit discussion.

Request for comments. The steps demonstrated in the examples could be implemented in a compiler if it makes any sense.

Definitions:

(=<*>) :: Monad m => m (a -> m b) -> m a -> m b
mf =<*> mx = join (mf <*> mx)
infixl 4 =<*>

LIFT1 (e0,p0)                 e1 = (\p0 ->               e1) <$> e0
LIFT2 (e0,p0) (e1,p1)         e2 = (\p0 -> \p1 ->        e2) <$> e0 <*> e1
LIFT3 (e0,p0) (e1,p1) (e2,p2) e3 = (\p0 -> \p1 -> \p2 -> e3) <$> e0 <*> e1 <*> e2
⋮

BIND1 (e0,p0)                 e1 = (\p0 ->               e1) =<< e0
BIND2 (e0,p0) (e1,p1)         e2 = (\p0 -> \p1 ->        e2) <$> e0 =<*> e1
BIND3 (e0,p0) (e1,p1) (e2,p2) e3 = (\p0 -> \p1 -> \p2 -> e3) <$> e0 <*> e1 =<*> e2
⋮

Example 0

do a <- foo
   b <- bar
   c <- baz
   d <- quux
   return (a,b,c,d)

foo >>= \a -> bar >>= \b -> baz >>= \c -> quux >>= \d -> return (a,b,c,d)

BIND1 (foo,a) (bar >>= \b -> baz >>= \c -> quux >>= \d -> return (a,b,c,d))

If the child expression is an application of (>>=) to an expression and a lambda expression, move them to the parent BIND.

BIND2 (foo,a) (bar,b) (baz >>= \c -> quux >>= \d -> return (a,b,c,d))

BIND3 (foo,a) (bar,b) (baz,c) (quux >>= \d -> return (a,b,c,d))

BIND4 (foo,a) (bar,b) (baz,c) (quux,d) (return (a,b,c,d))

If the child expression (with (.), ($) etc. inlined) is an application of return/pure to a value, change return/pure to id and BIND to LIFT.

LIFT4 (foo,a) (bar,b) (baz,c) (quux,d) (id (a,b,c,d))

(\a -> \b -> \c -> \d -> id (a,b,c,d)) <$> foo <*> bar <*> baz <*> quux

Example 1

do a <- foo
   b <- bar
   c <- baz a
   d <- quux
   return (a,b,c,d)

foo >>= \a -> bar >>= \b -> baz a >>= \c -> quux >>= \d -> return (a,b,c,d)

BIND1 (foo,a) (bar >>= \b -> baz a >>= \c -> quux >>= \d -> return (a,b,c,d))

BIND2 (foo,a) (bar,b) (baz a >>= \c -> quux >>= \d -> return (a,b,c,d))

baz a uses one of the variables bound in parent BIND. Start a new transformation.

BIND2 (foo,a) (bar,b) (BIND1 (baz a,c) (quux >>= \d -> return (a,b,c,d)))

BIND2 (foo,a) (bar,b) (BIND2 (baz a,c) (quux,d) (return (a,b,c,d)))

BIND2 (foo,a) (bar,b) (LIFT2 (baz a,c) (quux,d) (id (a,b,c,d)))

BIND2 (foo,a) (bar,b) ((\c -> \d -> id (a,b,c,d)) <$> baz a <*> quux)

(\a -> \b -> (\c -> \d -> id (a,b,c,d)) <$> baz a <*> quux) <$> foo =<*> bar