Mon Jan 17 10:38:11 EST 2011

Monadic let (a failed attempt at State continuation monad in Haskell)

For practical code generation we need at least the following

  - Continuation monad for let insertion.

  - State monad for variable names.

I'm lacking the ``muscle memory'' that comes with experience.  How do
we start this?  Essentially we want to make it easy to use, employing
standard `do' notation.  Let's start with what that would look like:

    f x y =
        a <- x + y
        return a * a

This gives an error message:

    Occurs check: cannot construct the infinite type: t = m t
      Expected type: m t
      Inferred type: t
    In the second argument of `(*)', namely `a'
    In the expression: return a * a

Ok, that is silly.  This one typechecks:

f4 x y =
      a <- x + y
      return (a * a)

So what does this mean?  It has the following type:

f4 :: (Num (m b), Monad m, Num b) => m b -> m b -> m b

Both the underlying type b and the monadic type (m b) need to behave
as a Num.  To summarize:

   Num b       from a * a
   Num (m b)   from x + y

So how to define the monad?  What confuses me is the type:
  m a -> (a -> m b) -> m b

I'd expect a == b.  Probably because I want to express a writer monad?
I'm getting frustrated.  It makes no sense...

Some questions.

  * What is the thing that is bound by `bind'?  Meaning the `a' type
    above?  It is a code expression.

  * Does it make sense to actually add monadic values?  Is it possible
    to only have 'let' be made explicit by using a do notation, and
    not any other form of combination?

    This means merging of dictonaries.  Do the examples in the paper
    use this?

  * How do the two types fit in this?  Why am I so conceptually stuck
    on "list append" ?