Damian Nadales Damian Nadales - 1 month ago 20
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 (
E
above). I would like to let this decision up to the interpreter. For instance,
E
could be a string, or a
Future
if we are creating objects with asynchronous REST calls.

If I try to define the DSL in the usual way using
liftF
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?

EDIT:

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

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.