Damian Nadales Damian Nadales - 10 months ago 71
Scala Question

Abstract result types in Free Monads

Suppose we want to define a simple DSL for defining UI interactions where we can create objects and then select them:

object TestCommand {

sealed trait EntityType
case object Project extends EntityType
case object Site extends EntityType

sealed trait TestCommand[A, E]
case class Create[A, E](entityType: EntityType, withEntity: E => A) extends TestCommand[A, E]
case class Select[A, E](entity: E, next: A) extends TestCommand[A, E]


The problem I have is that I wouldn't want to specify what the return type of the creation command should be (
above). I would like to let this decision up to the interpreter. For instance,
could be a string, or a
if we are creating objects with asynchronous REST calls.

If I try to define the DSL in the usual way using
as shown below:

object TestDSL {

def create[E](entityType: EntityType): Free[TestCommand[?, E], E] =
Free.liftF(Create(entityType, identity: E => E): TestCommand[E, E])

def select[E](entity: E): Free[TestCommand[?, E], Unit] =
Free.liftF(Select[Unit, E](entity, ()))


I get the following error:

Error:(10, 10) no type parameters for method liftF: (value: S[A])scalaz.Free[S,A] exist so that it can be applied to arguments (dsl.TestCommand.TestCommand[E,E])
--- because ---
argument expression's type is not compatible with formal parameter type;
found : dsl.TestCommand.TestCommand[E,E]
required: ?S[?A]
Free.liftF(Create(entityType, identity: E => E): TestCommand[E, E])

I cannot understand what is going wrong in the code above, but a more important question is whether this is the right way to abstract over the types appearing in free monads. If not, what is the right (functional) approach?


In Haskell the approach described above works without a problem:

{-# LANGUAGE DeriveFunctor #-}
-- |

module TestDSL where

import Control.Monad.Free

data EntityType = Project | Site

data TestCommand e a = Create EntityType (e -> a) | Select e a
deriving Functor

-- | The DSL
create :: EntityType -> Free (TestCommand e) e
create et = liftF $ Create et id

select :: e -> Free (TestCommand e) ()
select e = liftF $ Select e ()

-- | A sample program:
test :: Free (TestCommand e) ()
test = do
p <- create Project
select p
_ <- create Site
return ()

-- | A trivial interpreter.
interpTestCommand :: TestCommand String a -> IO a
interpTestCommand (Create Project withEntity) = do
putStrLn $ "Creating a project"
return (withEntity "Project X")
interpTestCommand (Create Site withEntity) = do
putStrLn $ "Creating a site"
return (withEntity "Site 51")
interpTestCommand (Select e next) = do
putStrLn $ "Selecting " ++ e
return next

-- | Running the interpreter
runTest :: IO ()
runTest = foldFree interpTestCommand test

Running the test will result in the following output:

λ> runTest
Creating a project
Selecting Project X
Creating a site

Answer Source

Right now you have test :: Free (TestCommand e) (). This means that the type of the entity e can be anything the caller wants, but it's fixed throughout the computation.

But that's not right! In the real world, the type of the entity that's created in response to a Create command depends on the command itself: if you created a Project then e should be Project; if you created a Site then e should be Site. So e shouldn't be fixed over the whole computation (because I might want to create Projects and Sites), and it shouldn't be up to the caller to pick an e.

Here's a solution in which the type of the entity depends on the value of the command.

data Site = Site { {- ... -} }
data Project = Project { {- ... -} }

data EntityType e where
    SiteTy :: EntityType Site
    ProjectTy :: EntityType Project

The idea here is that pattern-matching on an EntityType e tells you what its e is. In the Create command we'll existentially package up an entity e along with a bit of GADT evidence of the form EntityType e which you can pattern-match on to learn what e was.

data CommandF r where
    Create :: EntityType e -> (e -> r) -> CommandF r
    Select :: EntityType e -> e -> r -> CommandF r

instance Functor CommandF where
    fmap f (Create t next) = Create t (f . next)
    fmap f (Select t e next) = Select t e (f next)

type Command = Free CommandF

create :: EntityType e -> Command e
create t = Free (Create t Pure)

select :: EntityType e -> e -> Command ()
select t e = Free (Select t e (Pure ()))

myComputation :: Command ()
myComputation = do
    p <- create ProjectTy  -- p :: Project
    select ProjectTy p
    s <- create SiteTy  -- s :: Site
    return ()

When the interpreter reaches a Create instruction, its job is to return an entity of the type that matches the wrapped EntityType. It has to inspect the EntityType in order to know what e is and behave appropriately.

-- assuming createSite :: IO Site and createProject :: IO Project

interp :: CommandF a -> IO a
interp (Create SiteTy next) = do
    site <- createSite
    putStrLn "created a site"
    return (next site)
interp (Create ProjectTy next) = do
    project <- createProject
    putStrLn "created a project"
    return (next project)
-- plus clauses for Select

I don't know how this would translate into Scala exactly, but that's the gist of it in Haskell.