You can download the code for this example here
We motivated the previous presentation about monads by studying what happens when use
fmap :: Functor f => (a -> b) -> f a -> f b in conjunction with a function of type
a -> f b. Doing this produces the type
f (f b) and, when repeated, types such as
f (f (f b)), which were difficult to work with. However, for some functors, that we later decided to call
Monads, we could define the function
join :: (Monad m) => m (m a) -> m a, which can flatten such stacks of functors and make them easier to work with. However, there is another way to work with such structures. However, let us first construct an analogous, but simpler version of the same problem.
Consider what would happen if we tried to build a list of values using only tuples. At first, this seems quite easy:
tupleList = (1,(2,(3,(4,())))) thead = fst ttail = snd
However, when we inspect the types of such expressions, we find the same difficulty as we found when studying the nested functors: each such list would have a different type. For example, the type of list made out of tuples would change when the length of the list changes. For example a two element list would have a type
(Int,(Int,())) and a three element list would be described by
(Int,(Int,(Int, ()))). Notice that this would make general functions such as
filter quite challenging to implement.
The structure of caused by nested functors (ie.
f (f .. (f a))..)) gives a rise to a similar problem: different sequences of operations would have different types and are thus 'difficult' to operate with. Now consider the usual representation of a list, which solves this problem:
data List a = Cons a (List a) | Empty
Can we use the same idea to represent
f (f .. (f a)..)? Such representation for 'stack of functors' would have the non-recursive 'base' constructor containing the type
a (c.f ordinary list and
Empty) and a recursive constructor for storing the string of
Cons of an ordinary list).
data Free f a = Free (f (Free f a)) | Pure a data List a = Cons a (List a) | Empty
Contrast the above with the desugared definition of the list datatype: the list unifies the types of lists of all lengths, and the
Free f unifies the types of all 'stacks of functor'
Interestingly, it turns out that the type
Functor f => Free f a forms a monad regardless of the choice of the functor
f. This makes it an extremely general way of defining monads. As usual, it is easier to define the monad by first finding a suitable
join function. In this case, the join should have the type
Functor f => Free f (Free f a) -> Free f a, as the function has to turn a
Free containing another
Free into plain
Free. Writing such a function obeys the same principles as writing a recursive list processing function. Like in case of lists, we first define what to do in the non-recursive case. In this case, the non-recursive constructor is
Pure p (of the type
Free (Free f a)), where
p has the type
Free f a. It suffices to define:
joinF :: Functor f => Free f (Free f a) -> Free f a joinF (Pure p) = p joinF (Free fa) = ??
The case for the recursive constructor
Free is simple to define once we observe the type of
fa from above is
f (Free f (Free f a)). The only thing we can do with an arbitrary functor
f is to
fmap with some function. By observing the type of
joinF, it is immediately clear that
fmap joinF fa :: f (Free f a), which is almost exactly what we need:
joinF :: Functor f => Free f (Free f a) -> Free f a joinF (Free fa`fa :: f (Free f (Free f a))`, where `f` is a functor. ) = Free $ fmap joinF fa`fmap joinF fa :: f (Free f a)` --
return a = Pure a, we have a monad. If necessary, the related bind operators
>>= can similarly be distilled out of the type information (Exercise a).
Free monad can be used as a generic way of implementing other monads. For example, we have previously discovered such computations that log values during the computation can be considered as monads. The return value of such a computation could be
data Logged a = Logged String a deriving (Eq,Ord,Show)
where the type
a carries the return value of the computation. This type is obviously a functor, since
instance Functor Logged where fmap f (Logged s a) = Logged s (f a)
and we can wrap it inside
Free to make a monad. First, we create a function to create such wrapped values:
tell :: String -> Free Logged () tell s = Free (Logged s (Pure ()))
Free Logged a is a monad, we can do monadic things with it, such as to use the
do let a = 21 tell ("Responding to "++show a) let b = a*2 tell ("The answer is "++show x) return x
Notice however, that the monad
Free Logged a doesn't actually do anything besides recording the structure of the monadic computation. For example, the above is evaluated to
Free (Logged "Responding to 21" (Free (Logged "The answer is 42" (Pure 42)))). This result is just a value that represents the
stack of functors that motivated this discussion. We are free to do what ever we please with it. For example, we can define a similar behaviour as the original
Logged monad had:
runLogged (Pure r) = (,r) runLogged (Free (Tell r n)) = let (est,v) = runLogged n in (r:est,v)
Notice, that the above is essentially the same code that was used to implement
join for the original logging monad. Why did we bother with all the complexity then? One reason is that it gives us freedom to define multiple interpretations to what a computation returning a
Logged a means. We can, for example:
All this can be done post-facto writing the computations that use the
Logged a values.
You can download the code for this example here
A Domain Specific language is a programming language that has been designed to express solutions to programming tasks within a restricted domain. The idea behind such languages is to define a language that is especially suited to the problem domain without attempting to be applicable to other programming tasks. Examples of domain specific languages include SQL for manipulating relational databases and Verilog that is used to model electronics.
An Embedded Domain Specific Language (EDSL) is a domain specific language that is implemented on top of an existing (host) language. Such embedded language has the benefit of being able to access the operations of the host language and being automatically integratable to the the rest of the system.
Simple examples of EDSLs include sublanguages that
Free monads are naturallt suited to modelling embedded domain specific languages and can be used to do this in a systematic way. As an example, we will build a EDSL for defining computer opponents for an Asteroids like game. This EDSL will make it easier to define interesting behaviours for artificial opponents (ie. ufo's) and it will enable us to separate the controlling logic from the simulation of the game world. The end result will be an ufo that is aware of it's surroundings and can be programmed, for example, hunt the players ship:
hunterUFO :: Free UfoLanguage () hunterUFO = do dirToShip <- scan if (magV dirToShip > 100) then thrust p else do shoot p shoot p testUFO
First, we define operations that the UFO can perform. These are accelerating (
Thrust) observing it's surroundings (
Scan), shooting bullets (
Shoot) and shutting down (
Shutdown). The last operation is needed to model terminating programs.
data UfoLanguage next = Thrust Velocity next | Scan (PointInSpace -> next) | Shoot Velocity next | Shutdown
Each operation is modelled with a specific constructor and each constructor also holds the action that is done after the operation. For example, a simple program to scan the surroundings and shoot a bullet at the player could be encoded like this:
program1 = Scan (\playerLocation -> Shoot playerLocation Shutdown)
Firstly, we notice that the types of such expressions (see above) are quite complex which makes it hard to write any general operators for
Notice here that this problem has a form that is similar to the
tower of functors and we can solve this problem by wrapping
Free, which would make the types uniform and turn the
UfoLanguage into a monad. This is possible since
MiniLanguage a is a functor (Exercise b). Like before, the wrapping is done like this:
scan = Free (Scan (Pure . id)) thrust v = Free (Thrust v (Pure ())) shoot v = Free (Shoot v (Pure ())) done = Free Shutdown
Creating such wrappers can be greatly simplified by extracting the common part from each of the definitions to a re-usable function. (Exercise c)
With these wrappers, our language is embedded into the
Free datatype, which is a monad and we can start using the do notation without further ado. The example program from above can be written as:
-- Original: program1 = Scan (\playerLocation -> Shoot playerLocation Shutdown) program1' = do playerLocation <- scan shoot playerLocation shutdown
Notice that such embedding produces pure datum of the type
Free (UfoLanguage a) b. For example, the above program results in the expression
ree (Scan \(x,y)-> Free (Shoot (x,y) (Free Done))). We can now use the result in various ways, such as writing a function to print the resulting program (Exercise d). Or we can build a complete interpreter that actually executes this language (Exercise e), and use it as part of our Asteroids game:
updateUFO :: AsteroidWorld -> UFO -> (UFO, [Bullet]) updateUFO _ (UFO pos vel 0 (Free (Thrust v n))) = (updatedUfo pos vel (limitMag v 15) 10 n, ) updateUFO (Play _ (Ship p v) _ _) (UFO pos vel 0 (Free (Scan fn))) = (updatedUfo pos vel (0,0) 10 (fn (p-pos)), ) updateUFO _ (UFO pos vel 0 (Free (Shoot v n))) = (updatedUfo pos vel (0,0) 10 n, [Bullet pos (150 .* norm v) 0]) updateUFO _ (UFO pos vel t n) = (updatedUfo pos vel (0,0) (t-1) n, ) updatedUfo :: PointInSpace -> PointInSpace -> PointInSpace -> Int -> Program -> UFO updatedUfo pos vel acc t n = UFO (pos .+ vel) (0.8 .* vel .+ acc) t n
Exercise -- The `Free` what?
Observe the 'monadic' behaviour of
Free f a for different types of functors, such as
Maybe. How do they work?
Exercise -- Binds for `Free`
f is a functor and show that
Free f r is a
Monad by defining the bind operators. (Hint: This is almost impossible to do without knowing the exact type of each variable involved. Do yourself a favour and write them on a piece of paper.)
Exercise -- The `Free` log
Define variants of the
runLog function from above, that
Exercise -- UfoLanguage
UfoLanguage. Do not use
UfoLanguage vinto the type
Free UfoLanguage a. This is usually called liftF
. Notice that you need two of these. One for operations such asscan
that bring values into the computation and one for operations such asshoot`, that do not query information from outside world.
Show a => Free UfoLanguage a.
Clarity of presentation
Difficulty of the topic
Interestingness of the topic