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 f's (c.f. 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' f.
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)`
--
Since 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).
The 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 ()))
Since Free Logged a is a monad, we can do monadic things with it, such as to use the do notation:
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
Asteroids game with an ufo
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 UfoLanguage:
Notice here that this problem has a form that is similar to the tower of functors and we can solve this problem by wrapping UfoLanguage inside 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
Free what?Exercise -- The `Free` what?
Observe the 'monadic' behaviour of Free f a for different types of functors, such as Maybe. How do they work?
FreeExercise -- Binds for `Free`
Assume that 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.)
Free logExercise -- The `Free` log
Define variants of the runLog function from above, that
Exercise -- UfoLanguage
UfoLanguage. Do not use deriving (Functor).UfoLanguage v into the type Free UfoLanguage a. This is usually called liftF. Notice that you need two of these. One for operations such asscanthat bring values into the computation and one for operations such asshoot`, that do not query information from outside world.Show a => Free UfoLanguage a.UfoLanguage.Clarity of presentation
Difficulty of the topic
Interestingness of the topic
Detailed comments/Criticisms