Generalizing a monadic expression over a list of items

Question

I have a monadic function that helps translating values of type Expr to Term's. The signature is

fromDM :: (Name -> CompilerM Term) -> Expr -> CompilerM Term

I have trouble treating one case in general. I can write down implementations for every individual solution

import Control.Monad.State

type CompilerM = State Incr

newtype Incr = Incr Int deriving (Show)

generateNameM :: CompilerM Name
generateNameM = state $ \i ->
  let Incr y = i
      j      = (+1) y
  in  (Name j, Incr j)

data Expr = Tuple [Expr]
data Name = Name Int
data Term = Let Name [Name] Term

fromDM :: (Name -> CompilerM Term) -> Expr -> CompilerM Term
fromDM k expr = case expr of
  Tuple [e1, e2]         -> do
    x  <- generateNameM
    t' <- k x
    fromDM (\z1 -> fromDM (\z2 -> pure $ Let x [z1, z2] t') e2) e1

  Tuple [e1, e2, e3]     -> do
    x  <- generateNameM
    t' <- k x
    fromDM (\z1 -> fromDM (\z2 -> fromDM (\z3 -> pure $ Let x [z1, z2, z3] t') e3) e2) e1

  Tuple [e1, e2, e3, e4] -> do
    x  <- generateNameM
    t' <- k x
    fromDM (\z1 -> fromDM (\z2 -> fromDM (\z3 -> fromDM (\z4 -> return $ Let x [z1, z2, z3, z4] t') e4) e3) e2) e1

Now I want to substitute this with a general rule, i.e. Tuple es. I feel this should be doable with either foldlM or foldrM. Yet I am kind of stuck on how to do this. So, how do I write a general rule for this transformation that works on an arbitrary list of expressions?

Possible duplicate of [Is there a way to chain functions like withCString?](http://stackoverflow.com/questions/37379984/is-there-a-way-to-chain-functions-like-withcstring) — Cactus, Oct 16 '16 at 12:57
How is that question a duplicate? I unfortunately cannot map my question to the question or answers over there. — wirrbel, Oct 16 '16 at 13:24
It seems that you are having trouble composing your `fromDM` function calls because you have to nest the callbacks that handle the sub-results. It's the same pattern as composing `withCString` etc., by turning the nesting structure inside-out via `Cont`. — Cactus, Oct 16 '16 at 13:56
@data_hope I agree that the remarks are opaque so far, and the the question is in no sense a duplicate. But ContT is the right idea. Note that `\e -> ContT (flip fromDM e) :: Expr -> ContT Term CompilerM Name` if I have the order right. It is hard to get a handle on it with so little source. — Michael, Oct 16 '16 at 14:03
Alright, I updated the snippet so that it is at least a compilable self-contained piece of code. I suppose that one could find a solution to generalize that pattern. I will also have a look at `Cont`/`ContT`. — wirrbel, Oct 16 '16 at 14:21
@Michael thank you, it is really neat (and Cont seems to be a very useful monad). — wirrbel, Oct 16 '16 at 15:22
@data_hope I can't tell what else is going on, so maybe this is wrong, but things like `fromDM` might be put entirely in `ContT` See this http://sprunge.us/gZbQ We might even write `type Compiler a = ContT Term (State Incr) a` — Michael, Oct 16 '16 at 15:42
@Michael Having a closer look at http://sprunge.us/gZbQ , indeed I think `type Compiler = ContT Term (State Incr)` was applicable with my code. — wirrbel, Oct 16 '16 at 19:33

score 2 · Accepted Answer · answered Oct 16 '16 at 19:44

Okay, I don't know much about Cont, so let me outline my thought process when I approached this question. The first thing I wanted to do was to pull out only the bits of code that depend on the contents of the Tuple, thus:

fromDM k expr = case expr of
    Tuple es -> do
        x  <- generateNameM
        t' <- k x
        letExprs x t' es

letExprs x t' [e1, e2] = fromDM (\z1 -> fromDM (\z2 -> pure $ Let x [z1, z2] t') e2) e1
-- etc.

We would like to abstract letExprs so that it can work on lists of any length. Now that we've written down the problem, the next step in the Feynman protocol is to Think Very Hard. So I stared Very Hard at the different cases. It looked to me like each cons cell in the list turned into a call to fromDM; and in the base case, the Let was applied to a varying list. We can stick the varying list in an accumulator, like this:

fromDM k expr = case expr of
    Tuple es -> do
        x  <- generateNameM
        t' <- k x
        letExprs x t' [] es

letExprs x t' vars [] = pure $ Let x (reverse vars) t'
letExprs x t' vars (e:es) = fromDM (\z -> letExprs x t' (z:vars) es) e

This already looks pretty good to me. If you want to turn it into a fold (which is nice for the usual reasons: you can't accidentally screw up the recursion pattern, and readers know you're not doing anything tricky), we can now almost read it off directly:

fromDM k expr = case expr of
    Tuple es -> do
        x  <- generateNameM
        t' <- k x
        foldr (\e k vars -> fromDM (\z -> k (z:vars)) e)
              (\vars -> pure $ Let x (reverse vars) t')
              es

Looks great; we could simplify a bit because `Expr` only ever has a single case, thus `fromDM k (Tuple es) = do ...` — Yawar, Oct 16 '16 at 19:52
@Yawar Presumably this is a reduction of a more complicated collection of data types, so I tried to maintain the original code style wherever I could. — Daniel Wagner, Oct 16 '16 at 19:53

Generalizing a monadic expression over a list of items

1 Answers1