makeOps for free!

[fizruk]

Currently anyone using free monads is forced to write some boilerplate code, e.g.:

data Lang next
  = Output String next
  | Input (String -> next)
  | Done
  deriving (Functor)

-- here goes boilerplate code...
output :: (MonadFree Lang m) => String -> m ()
output s = liftF $ Output s ()

input :: (MonadFree Lang m) => m String
input = liftF $ Input id

done :: (MonadFree Lang m) => m a
done = liftF Done

I'd be happy to substitute that with:

data Lang next
  = Output String next
  | Input (String -> next)
  | Done
  deriving (Functor)
makeOps ''Lang

I'm not sure this can be done in general, but there certainly is some pattern we could probably use. I am not familiar with TH enough to implement the idea right now.

Also I guess this TH stuff should be placed in a separate package?

[bgamari]

I'm not sure I see how the input definition could be mechanically derived.

[fizruk]

Basically a data type representing underlying functor looks like that:

data T next = C1 u v w | C2 x y z | ...

For each constructor we want to define an appropriate "free operation":

• operation name is derived by lowering the first letter: Op => op, SomeCtor => someCtor;
• if constructor has arguments that don't depend on next they are used as arguments to the corresponding operation;
• if constructor does not have arguments that depend on next then the operation is of type op :: (MonadFree f m) => b -> c -> ... -> m a and is defined simply as op x ... z = liftM $ Op x ... z;
• for each argument for constructor that depend on next the following rules are applied:
  • next goes to ()
  • a -> next goes to id
  • a -> b -> next goes to (,)
  • similarly, a -> ... -> z -> next goes to (,,...,)
  • for arbitrary type T rules apply recursively with 2 considerations:
    • a tuple (a, b, ..., z) should be seen as separate "arguments" a, b, ..., z if any of components use next;
    • alternatives in types like Either should result in branching operations, e.g.:

data MyOps next
  = Move (MoveDir next)
  | Stop

data MoveDir next
  = Left next
  | Right next
  | Down next
  | Up next

-- automatic derivation of operations for `MyOps` should result in 5 operations
-- names are derived by appending constructor names
moveLeft = ...
moveRight = ...
moveUp = ...
moveDown = ...
stop = ...

The last thing is debatable (about sum types). I hope this covers most of uses.

[fizruk]

Here are some examples with desired derivations:

data F next
  = Done
  | Failure String
  | Delay next
  | Output String next
  | Input (String -> next)
  | GetMsg (Int -> String -> next)
  | Prompt String (String -> next)
  | Branch next next
  | Cont ((next -> Int) -> Int)
  | Doing (Maybe next)
  deriving (Functor)

-- desired derivations
done :: MonadFree F m => m a
done = liftF Done

failure :: MonadFree F m => String -> m a
failure s = liftF $ Failure s

delay :: MonadFree F m => m ()
delay = liftF $ Delay ()

output :: MonadFree F m => String -> m ()
output s = liftF $ Output s ()

input :: MonadFree F m => m String
input = liftF $ Input id

getMsg :: MonadFree F m => m (Int, String)
getMsg = liftF $ GetMsg (,)

prompt :: MonadFree F m => String -> m String
prompt s = liftF $ Prompt s id

branch :: MonadFree F m => m ()
branch = liftF $ Branch () ()

cont :: (MonadFree F m) => m ()
cont = liftF $ Cont (\k -> k ())

doingNothing :: MonadFree F m => m a
doingNothing = liftF $ Doing Nothing

doingJust :: MonadFree F m => m ()
doingJust = liftF $ Doing $ Just ()

I still don't know how to handle recursive definitions (or should they be handled). E.g. for [a] or Tree a.

[bgamari]

Things are complicated when one considers cases such as,

data Foo a = Foo (String -> a) (Int -> a)

In this case you might want the operation to be something like,

foo :: MonadFree Foo m => m (Either String Int)

but in general it won't be possible to construct a sum type like this.

For now it'll be sufficient to consider the simple cases like Foo and,

data Bar a = Bar a (String -> a)
bar :: MonadFree Bar m => m (Maybe String)

[bgamari]

@fizruk brought up the point that one could also derive cases like,

data Bar' a  = Bar' a a (String -> a)

bar' :: MonadFree Bar' m => m (Maybe a)
bar' = Bar' Nothing Nothing Just

It's not entirely clear that we want to do this however.

[bgamari]

I started working on this today in an effort to avoid writing a talk. The (currently broken) state of things can be found here. I'll keep updating this as I do more work on it.

[fizruk]

Digging into gist by @bgamari, I got working code for simplest cases https://gist.github.com/fizruk/7441605.

[fizruk]

Okay, I believe now this supports most of the basic stuff (the code should be refined though).

@ekmett, what do think about all this? Where should such a thing be placed? Control.Monad.Free.TH or a separate package (e.g. free-derive)?

[ekmett]

I'd be okay with adding it directly to the package here if folks want it.

[fizruk]

Interestingly, there is another kind of operations which could also be derived automatically. Consider this:

data Expr e
  = Lit Int
  | Add e e
  deriving (Functor)

lit :: MonadFree Expr m => m a
lit x = wrap $ Lit x

add :: MonadFree Expr m => m a -> m a -> m a
add x y = wrap $ Add x y

Those can be used like that:

data Term = Free Expr Void

test :: Term
test = add (lit 4) (lit 5)

I don't use these operations, so I can't see if automatic generation for them is needed (but perhaps would be useful).

[ekmett]

Closing this as it is merged in.