First things first: If you only care about the code, here's the repo on github.

While learning a bit of Haskell I stumbled across the idea that one can use something called Free Monad to represent an abstract syntax tree of domain-specific languages. Since my Haskell-fu is still not too great, I didn't immediately understand that blog post. However, my interest was piqued. Domain specific languages, encoded in an easy to interpret syntax tree, sound like a nice building block for high-level game logic, after all.

The first thing I tried was to follow the example in the linked blog post to implement a small domain specific language for the domain of spending a night drinking in several bars, with varing beer temperature. It took me unreasonably long to add the functionality to stop drinking the first time a lukewarm beer gets served... Of course at the Le Rieur Sanglier. Let's better not talk too much about the full Haskell code of that experiment...

Still, I didn't feel like I actually understood what I was doing. So, I went ahead and tried to understand the maths behind Free Monads. Since I don't have a solid background in Category Theory, I couldn't claim with confidence that I understood it though...

This made me decide to learn more about category theory at some point, but for the moment I chose to follow a more pragmatic approach: Learnign by doing. In this case that means implementing the Free type (or a close-enough approximation) in Rust.

The obvious requirement of implementing a Free Monad is the ability to express what a Monad is. Writing a Monad trait was really difficult in Rust until recently. Luckily, Generic Associated Types are stable meanwhile, what makes it possible to implement a type trait for `Monad`

without the need for a workaround. The "higher" crate does just that, with some nice extras like do-notation, and I decided to use it as a basis for my own experiments.

The next ingredient is the actual `Free`

type. Rust does not have higher kinded types, so, where in Haskell one would just write `data Free f a = Pure a | Free (f (Free f a))`

, the closest thing one could do in Rust would be `enum Free<A,G>{ Pure(A), Free(G) }`

with further constraints on the respective trait implementations. But `G`

depends on `A`

, so, after mapping/binding we end up with a different `G`

. For now, let us not bother about this, the problems will show up soon enough.

In addition, we need an indirection. Since `G`

will be referencing `Free<A,G>`

, it needs to be put behind some smart pointer. Since (nearly) all trait methods in "higher" demand ownership of the passed-in values, and some types in "higher" like `ApplyFn`

do not implement `Clone`

, this needs to be a smart pointer that allows the code to take ownership without the need to copy its data. This pretty much limits the usage to `Box`

, which is *special* in that regard. In other words, our actual type will be more along the lines of `enum Free<A,G>{ Pure(A), Free(Box<G>) }`

. This is still fine though, because for almost all intents and purposes, `Box`

is transparent.

Now, in order to turn this type into a `Monad`

, we just have to implement a few traits from "higher" on it: `Functor`

, `Pure`

, `Apply`

, and `Bind`

. This sounds easy enough, right?

With that in mind, we can start hacking:

```
enum Free<A,G>{
```

Pure(A),

Free(Box<G>)

}

impl<'a, A, G> Functor<'a, A> for Free<A,G>

where G : Functor<'a, Self>

{

type Target<T> = Free<T,???>

fn fmap<B, F>(self, f: F) -> Self::Target<B> {

todo!()

}

}

Now, we hit the problem mentioned before. How are we supposed to express the type that `G`

becomes in the GAT? Trying to write it by hand we end up with `type Target<T> = Free<T, G::Target<Free<T, G::Target<Free<T, G::Target<Free<T,...>>>>>>>`

. However, we could try to refer to `Self`

to escape this: `type Target<T> = Free<T, G::Target<Self::Target<T>>>`

. This looks promising, except for the little issue that the compiler tries to replace it with `type Target<T> = Free<T, G::Target<Free<T, G::Target<Free<T, G::Target<Free<T,...>>>>>>>`

again...

Obviously this leads nowhere. Type aliases in Rust cannot be recursive. Therefore the type signature of the Free Monad type has to look different.

The problem obviously arises, because the second type parameter of the `enum Free<A,G>`

depends on the first one. But there is a rather trivial way to get rid of it, by using a newtype:

`struct ConcreteFree<A>(Free<A,ConcreteFunctorType<Self>>)`

Unlike type aliases, actual types in Rust can be recursive. While this obviously works, it would require implementing the traits needed for it to be a `Monad`

for every newtype of this shape. That sounds like the perfect job for a macro though.

However, if the type is already generated by a macro, the newtype is no longer necessary. The macro could just directly implement the `enum ConcreteFree<A>`

. While implementing `Functor`

and `Bind`

for this macro-generated type, we run into an obstacle in the form of ownership of the mapping function:

```
impl<'a,A> Functor<'a,A> for $name<A> {
```

type Target<T> = $name<T>;

fn fmap<B,F>(self, f: F) -> Self::Target<B> where F: Fn(A) -> B + 'a{

match self{

$name::Pure(a) => $name::Pure(f(a)),

$name::Free(fa) => {$name::Free(Box::new(fa.fmap(|x| x.fmap(f))))},

}

}

The problem is that `f`

gets moved out of the closure in the `$name::Free(fa)`

match arm, because there is no guarantee that `fa.fmap()`

doesn't call the closure multiple times.

This is important enough to highlight it, and to add an interlude instead of going directly to the fix for the issue, because this one compile error is actually what captures the essence of a Free Monad from a programmer's perspective. In other words, this was the point at which the little hamster living in my brain jumped into its wheel and started spinning it.

My own mental picture, which is a gross oversimplification and ignores all mathematical details, is actually a rather simple one. A Free Monad builds up a tree of nodes. The nodes can either be leaf-nodes and contain a value (Pure), or can be inner nodes (Free) with child-nodes, the structure of which is imposed by the Functor the Free Monad is based on. Free nodes can also be leaf-nodes though, in case the Functor has states that hold no data, for instance `Option::None`

. Free nodes can hold values too, but those values are not affected by map/bind/... The monadic operations performed on a Free Monad traverse it (depth first), and only affect the `Pure`

nodes. For instance, `a.apply(f)`

traverses the Free Monad `f`

, and replaces any `Pure`

it finds with `a.fmap(v)`

, where `v`

is the value (in this case: a function) stored in the Pure node. The result of `a.apply(f)`

is therefore a tree where each previous `Pure`

has been replaced by a sub-tree that looks like `a`

, and holds the mapped values in its `Pure`

nodes. Or, as a simler example, let's take `a.bind(f)`

. The function `f`

returns a Free Monad too, so what this does is that every `Pure`

in `a`

gets replaced by the result of `f`

applied to its value. And, the most simple example, `a.fmap(f)`

, just replaces each `Pure`

in `a`

by another `Pure`

, now holding the mapped value.

`a.fmap(f)`

map?
Sometimes a picture says more than a thousand words. For these drawings, let's just take a list with 2 elements as our Functor. The most simple operation is `a.fmap(f)`

where `f : Fn(A)->B`

. Let's just assume our `a`

looks like this:

In the case of `a.fmap(f)`

the shape of the Free Monad doesn't change. Just the values in the Pure nodes are replaced:

`a.bind(f)`

?
`a.bind(f)`

is rather similar to `a.fmap(f)`

, but the signature of `f`

is different: `f : Fn(A)->Free<B>`

. So, instead of replacing every Pure node by another Pure node, `a.bind(f)`

can replace individual nodes by whole sub-trees. Let's start with the same example tree again:

This gets replaced by:

If, for example, `f(b)=Pure x`

, `f(c)=Free(Pure y, Pure z)`

and `f(d)=Pure w`

, the result of `a.bind(f)`

would be this tree:

`a.apply(f)`

apply?
Last, let us take a look at an example of `a.apply(f)`

, where `f`

is given by this tree:

If we now call `a.apply(f)`

, the result would become

For example, if `a`

would be this tree:

The result of `a.apply(f)`

would then look like this:

As you can see, the shape after `a.apply(f)`

matches `f`

, with every `Pure x`

replaced by the result of calling `a.fmap(x)`

.

Please also keep in mind that the tree-picture is just that, a mental picture. The actual data structure can be more complicated than that. For instance, if the Functor uses continuation functions (see below), the actual shape of a branch can depend on values that are only supplied after its creation. Of course it still behaves like a tree, but the branches are created in a lazy manner then.

This structure can be used to express embedded domain specific languages in a rather simple manner, especially when combined with do-notation:

- Commands are
`Free`

nodes. To append a command to a program, one can use`bind()`

to replace the previous`Pure`

nodes with it. By default, new commands contain "default"`Pure`

nodes. - Return values are stored in
`Pure`

nodes. That way, the next command that gets appended with`bind()`

can take that value as parameter. When using do-notation, it can be assigned to a name, and commands further down can refer to it. - To accept input from the interpreter of the eDSL,
`Free`

nodes can contain a continuation function that takes that value as input parameter, and returns the remainder of the tree that depends on the input. This will get more clear once we get to an actual example.

In case you don't know do-notation, a short reminder how it works. It's syntax sugar over chained `bind()`

calls. Using the syntax from higher's `run!()`

macro, it works like this:

```
run!{
```

will be translated into

a;

b;

...

}

```
a.bind(move |_| { b.bind(move |_| { ... } ) } );
```

and values can be bound to names like this:

```
run!{
```

which will be converted into

x <= a;

b;

...

}

```
a.bind(move |x| { b.bind(move |_| { ... } ) } );
```

This is what makes the Free Monad so awesome for eDSL usage. You can write the script in your eDSL within do-notation. Every new statement gets appended after the previous one. In the end you build a data structure, but it feels like just writing an imperative program. Branching can be expressed too, because, as we have seen, `bind()`

appends the new code instead of every Pure node. Since desugaring creates nested closures, you can refer to previously created names in following statements. Also, the individual "statements" are actually functions returning a `Free`

, so you can use syntax from the host-language (in this case Rust) in them. To see it in action, check the example below.

I know, I wrote that this ignores all mathematical details, but one thing I have to mention: By its very definition, a Free Monad obays the Monad laws as long as the Functor it is based on obeys the Functor laws. In other words, for our eDSL use case, we really need to make sure our Functor is actually a lawful Functor, not only something just implementing the trait.

All that thinking about the properties of Functors and the Free Monad got the hamster wheel in my brain spinning quite fast. And just before the hamster got a heart attack, a thought was produced: If the Functor we use as a basis for our Free Monad obeys the Functor laws, especially the one regarding the composition of morphisms, then the `Functor<'a,A>::Target<T>`

*must not* depend on `A`

. Or, in other words,

`∀A∀B∀C : Functor<A>::Target<B>::Target<C> = Functor<A>::Target<C>`

.

This sounds like something that we might be able to convey to the Rust compiler, in order to eliminate the Functor's exact type from Free's type signature. This also sounds like a perfect use case for the `!`

type to express that the type in the signature will never actually be constructed:

```
use never_say_never::Never;
```

enum Free<'a,A,F> where F : Functor<'a,Never>{

Pure(A),

Free(Box<F::Target<Self>>)

}

impl<'a,A,G> Free<'a,A,G> where G : Functor<'a,Never>{

fn __fmap_impl<B, F>(self, f: &'a F) -> Free<'a,B,G>

where F: Fn(A) -> B + 'a,

G::Target::<Self> : Functor<'a, Self, Target<Free<'a,B,G>> = G::Target<Free<'a,B,G>>>

{

match self {

Free::Pure(a) => {Free::Pure(f(a))},

Free::Free(fa) => {

Free::<'a,B,G>::Free(Box::new(

fa.fmap(|x| x.__fmap_impl(f))

))

},

}

}

}

This actually compiles in current Stable Rust. Also, this includes the fix for the issue we had above. Instead of consuming the mapping function, we take a reference to it. But now we have another issue: The trait bound expressing that we are dealing with a lawful Functor is on the fmap function. If we try to implement the `Functor`

trait, we have no way to express this, because putting the same constraint on the `fmap()`

function causes [E0276]: impl has stricter requirements than trait. If only there was a syntax in Rust to express `∀B`

... Then we could actually move that bound to the trait implementation itself... But this is certainly something we can only dream of, right?

While dreaming about syntax is nice, it doesn't help solving the problem at hand, namely implementing a Free Monad type in Rust. With the new knowledge that it's possible to work around the move of the mapping function in `Bind`

and `Functor`

by using a reference instead of the function itself, it's now actually straightforward to implement those operations for `Free<A>`

. To make this work with the traits from `higher`

, it's enough to move the actual implementation into a separate function that takes `&f`

instead of `f`

, and have the trait function call that one.

```
impl<'a,A> Functor<'a,A> for $name<A> {
```

type Target<T> = $name<T>;

fn fmap<B,F>(self, f: F) -> Self::Target<B> where F: Fn(A) -> B + 'a{

self.__fmap_impl(&f)

}

}

`Pure`

is straightforward to implement and `Bind`

is nearly identical to `Functor`

, so only `Apply`

is left. This one causes troubles though. As we now know, a Free Monad is like a tree, and `a.apply(f)`

replaces each `Pure`

in `f`

with the Free Monad obtained by calling `a.fmap()`

with the function stored in that `Pure`

. This means, that we have to call `a.fmap()`

multiple times, but `a.fmap()`

consumes `a`

... The easy way out is to require that `a`

is `Clone`

. While this isn't the nicest requirement, `higher`

also needs it for its `Apply`

implementation for `Vec`

, so at least in that regard the Free Monad is in good company. Furthermore, there is no real reason that `Monad`

requires `Apply`

. That's just because Haskell has this requirement for historical reasons, not because the maths behind Monads would require it. One could therefore just roll a `trait MyOwnMonadWithBlackjackAndHookers : Functor + Bind + Pure`

and use that one instead of the actual `Monad`

from `higher`

.

Another challenge here is that just porting over the `Apply`

source code from Haskell's Free type would cause an insane amount of deep copies. Luckily there is a generic `Apply`

function in `higher`

that one can use: `higher::apply::ap(f,a)`

. This is way better suited for Rust code, because it only makes one deep copy of `a`

per `Pure`

node in `f`

. This function is actually the generic `Apply`

implementation that works for every type that is `Bind`

and `Pure`

.

By the way, the deep copies could be eliminated completely be replacing the `Box`

in the type by a shared reference. However, `Box`

has unique ownership, and therefore allows to move out of it if one owns the `Box`

(because `Box`

is special). Shared references only allow moving out if the reference count is exactly 1. That means that if we used a shared reference, all `Functor`

and `Bind`

would require `Clone`

too as a fallback if the reference count is not 1. I consider this additional requirement much worse than suboptimal performance in `Apply`

.

With this, our macro can now generate Free Monads for any arbitrary Functor. To make it a bit more useable, `lift_f(a)`

and `retract(m)`

are still missing. The function signatures for those are a bit weird, but nothing too bad:

```
impl<$generic> $name<$generic>{
```

$v fn lift_f(command : <$f as $crate::higher::Functor<Self>>::Target<$generic>) -> Self{

use $crate::higher::Functor;

Self::Free(Box::new(command.fmap(|a| Self::Pure(a))))

}

$v fn retract<'a>(self) -> <$f as $crate::higher::Bind<'a,Self>>::Target<$generic>

where $f : $crate::higher::Monad<'a,Self>,

<$f as $crate::higher::Bind<'a,Self>>::Target<$generic> : $crate::higher::Pure<$generic>

{

use $crate::higher::{Bind, Pure};

match self {

$name::Pure(a) => {<$f as $crate::higher::Bind<'a,Self>>::Target::<$generic>::pure(a)},

$name::Free(m) => {m.bind(|a| a.retract())}

}

}

}

And with that, everything was looking great. Except that lifetimes would like to have a word... In our use case of domain specific languages, we have to deal with continuation functions, for which a Functor needs to use function composition to remain lawful. And this means the output of `Functor`

and `Bind`

can reference the mapping function itself. In other words, lifetime annotations are needed, and the trick we used above to work around the need to copy the mapping function doesn't work in that case. Imposing `Clone`

is also not possible, because the mapping functions are not known at the `impl`

-level...

Luckily we can just use shared references here (remember, a Free Monad is tree-like, so there are no reference cycles possible). So, instead of `__fmap_impl(self, f : &F)`

we can simply use `__fmap_impl(self, f : Rc<F>)`

and everything is good again.

Of course this is now an understatement of the actual amount of work that went into making the macro lifetime-aware, and I'm pretty certain that there are still bugs hidden somewhere in that code.

But long story short, the resulting code is now available in the higher-free-macro project on github.

Turns out, the dream mentioned above started to became reality a few days ago. Non-Lifetime binders were merged to Nightly Rust.

This awesome new language feature allows us to write a generic Free Monad. The linked playground compiles just fine with the nightly toolchain. It is a bit clunky to use, as the cycle in the `Clone`

implementation needs to be broken by hand, so `#[derive(Clone)]`

is not an option... However, the general idea is working.

The usage of the `enum Free<A,F>`

on the linked playground is straightforward. `A`

is the type of the value in `Free::Pure`

, and `F`

is the `Functor`

the Free Monad is based on, specialized for the `!`

Never Type. For instance, to get a Free Monad for a Functor `TestFunctor<A>`

, one could simply use the type `Free<A,TestFunctor<!>>`

. To make it a Monad, one also has to convince the compiler, that `Clone`

is working. Deriving it currently does not work. See the Playground for details.

This section has been updated on 2023-03-16 to reflect recent changes to the macro. Previously it was not possible to base a Free Monad on a Functor type for which the result of `fmap(f)`

does not depend on the lifetime of `f`

, but which has named lifetime parameters. This has been fixed meanwhile, but at the cost of making the macro usage a bit more complicated.

Unless someone finds a clever way to do a generic implementation in Stable Rust, we are stuck with the macro-based one though. However, it's actually quite convenient to use.

In order to declare a new Free Monad type for our Functor type, all we need to do is to call the `free!()`

macro with the right parameters. Let's look at an example. Here `Saturday<'a,A>`

is a `Functor<'a,A>`

, for which the lifetime of the result of `fmap(f)`

depends on the lifetime of `f : fn(A)->B + 'a`

. The Free Monad based on it can be declared like this: `free!(<'a>, pub FreeSaturday<'a, A>, Saturday<'a,FreeSaturday<'a, A>>);`

. The `pub`

is optional, you can add it if you want your type to be public. The first parameter to the macro (`<'a>`

) denotes the lifetime to which the result of the different operations on the Free Monad should be tied. If the result of the operations does not depend on the lifetime of the functor's mapping function, the first parameter needs to be omitted. For instance, a Free Monad based on `Option<T>`

would be declared like this: `free!(FreeOption<T>, Option<FreeOption<T>>)`

.

The above is still rather dry. Let's have a quick glimpse at a full eDSL example now, to see how we can use do-notation to plan a nice Saturday evening.

We start with the usual boilerplate, and then define our Functor, `Saturday`

. It has two commands for our language. Either we can go to a different bar, or drink a beer at the location we are at right now. Both commands have a continuation function, `Next`

. For the use case as eDSL we want these continuation functions to be pure. In Nightly rust, we could use const_trait_impl and const_closures to actually enforce this. Since none of these features are stable yet, for now we just have to be careful to not write impure code by accident... In any case, under the assumption that the continuation function is pure, it can be replaced by its return value, if it doesn't take any parameters. This is for instance the case for `GoToBar`

. Here, `Next`

is just a value, not a function. In the case `DrinkABeer`

the return value of the continuation function depends on the `BeerQuality`

at the current bar. This value is only known when we actually taste the beer there (as in: cause a side-effect). So, our (hopefully) pure Free Monad needs to store an actual `Fn(BeerQuality)->Next`

. We do not want this function to show up in the type signature though, because that would make it quite impossible to implement `Functor`

for `Saturday`

. Also, we want to make `Saturday`

cloneable, to allow `Apply`

to be implemented for it. That's why the actual type of the continuation will be a shared reference to a trait object. Also, please note the `+'a`

on the continuation function. This is used to tie it to the lifetime of the function passed to `fmap(f)`

in the `Functor`

implementation below.

```
use std::rc::Rc
```

use higher_free_macro::free;

use higher::*;

#[derive(Debug, Clone, PartialEq)]

enum BeerQuality{

Lukewarm,

Refreshing

}

#[derive(Clone)]

enum Saturday<'a, Next>{

GoToBar{

name_of_bar : &'a str,

next : Next

},

DrinkABeer (Rc<dyn Fn(BeerQuality)->Next + 'a>) //Rc, because it's cloneable, dyn to keep it out of the type signature.

}

When implementing `Functor`

for `Saturday`

we need to keep the Functor Laws in mind. Sadly we can't just use the `#[derive(Functor)]`

macro from "higher", as our `Saturday`

is too complex for it to work. Otherwise this would be a trivial task... But well, here it's actually rather easy too. For `GoToBar`

we can just map eagerly, because we are dealing with values. For `DrinkABeer`

, where we evaluate the continuation lazily (as in: during interpretation of the Free Monad), we instead do function composition. As noted above, we tie the lifetime of the continuation function in `DrinkABeer`

to the function passed to `fmap(f)`

:

```
impl<'a, Next : 'a> Functor<'a, Next> for Saturday<'a, Next>{
```

type Target<T> = Saturday<'a, T>;

fn fmap<B, F>(self, f: F) -> Self::Target<B>

where F: Fn(Next) -> B + 'a {

match self {

Saturday::GoToBar { name_of_bar, next } => {

Saturday::GoToBar { name_of_bar, next: f(next) }

},

Saturday::DrinkABeer(continuation) => {

Saturday::DrinkABeer(Rc::new(move |x| f(continuation(x))))

},

}

}

}

Next the magic happens. We call the `free!()`

macro to generate the Free Monad `FreeSaturday`

, based on the `Saturday`

Functor.

```
free!(<'a>, FreeSaturday<'a, A>, Saturday<'a,FreeSaturday<'a, A>>);
```

It's convenient to have simple functions to create each `Free`

variant, containing a `Pure`

as continuation. These functions are the "commands" we run in do-notation later.

```
fn go_to_bar(s : &str) -> FreeSaturday<'_, ()>{
```

FreeSaturday::lift_f(

Saturday::GoToBar { name_of_bar: s, next: () }

)

}

fn drink_a_beer<'a>() -> FreeSaturday<'a, BeerQuality>{

FreeSaturday::lift_f(

Saturday::DrinkABeer(

Rc::new(std::convert::identity)

)

)

}

Now we have all ingredients ready to actually write down the plan for a nice evening. We do that using, well, do-notation. In "higher" it's called `run!{}`

. It's worth checking out the source code of run!{}, because it shows how elegant declarative macros in Rust can be.

Here we can see the signature of `fn drink_a_beer<'a>() -> FreeSaturday<'a, BeerQuality>`

in action. As noted above, in order to consume input from the interpreter later, we can build continuation functions that take an input parameter. Furthermore, the helper `drink_a_beer()`

returns `FreeSaturday<'a, BeerQuality>`

, meaning it has a *return value* of type `BeerQuality`

, for which we can bind an identifier with the `<=`

operator of `run!{}`

. It is worth noting that, while in this case the return value is from a side effect the interpreter has to deal with, that's a pattern that can also be used for methods within the eDSL.

In a perfect world, we would make this a `const`

function, just like we would make the continuation functions in the Functor const - to rule out any side effects. As far as I know this is not possible in Stable Rust, so we have to make sure everything in here is pure by hand...

The plan for the evening is by the way rather simple: If we get served a lukewarm beer, we stop drinking.

```
fn a_nice_evening() -> FreeSaturday<'static,()>{
```

run! {

drink_a_beer(); //at home. Don't care if lukewarm.

go_to_bar("Sunken Norwegian");

x <= drink_a_beer();

if x != BeerQuality::Lukewarm { run! {

drink_a_beer(); //alredy know if the beer here was lukewarm or not.

go_to_bar("Le Rieur Sanglier");

x <= drink_a_beer();

if x != BeerQuality::Lukewarm { run! {

drink_a_beer();

go_to_bar("Coyote Ugly");

x <= drink_a_beer();

if x != BeerQuality::Lukewarm { run! {

drink_a_beer();

yield ()

}} else{ run! { yield () } }

}} else{ run! { yield () } }

}} else{ run! { yield () } }

}

}

We can actually prove that the return value of `a_nice_evening()`

is a `Monad`

:

```
fn _test_if_a_nice_evening_is_monad() -> impl Monad<'static, ()>{
```

a_nice_evening()

}

Last, but not least, here we have an example interpreter that actually runs the above plan. This is now the location, where we actually know if we get lukewarm beer.

This interpreter just counts how many beers we consumed at each bar. There isn't much notable about it, except that it calls `get_beer_quality_of_location()`

in case it encounters a `DrinkABeer`

command, to actually run the continuation function.

```
fn count_beers_consumed_per_bar(evening : FreeSaturday<()>) -> Vec<(&str, u32)>{
```

//let's assume get_beer_quality_of_location() has side effects.

fn get_beer_quality_of_location(l : &str) -> BeerQuality {

if l == "Le Rieur Sanglier" {

BeerQuality::Lukewarm

} else {

BeerQuality::Refreshing

}

}

fn interpret_evening_step<'a, 'b : 'a>(

l : &'b str,

mut v : Vec<(&'a str, u32)>,

saturday : FreeSaturday<'b,()>

) -> Vec<(&'a str, u32)>{

match (l,&*v,saturday){

(_,_,FreeSaturday::Pure(_)) => v,

(l, [.., (lo,co)], FreeSaturday::Free(f)) if *lo == l=> {

match *f {

Saturday::GoToBar { name_of_bar, next } =>

interpret_evening_step(name_of_bar, v, next),

Saturday::DrinkABeer(next) => {

v.last_mut().unwrap().1 = co+1;

interpret_evening_step(l, v, next(get_beer_quality_of_location(l)))

}

}

}

(l, _, FreeSaturday::Free(f)) => {

match *f {

Saturday::GoToBar { name_of_bar, next } =>

interpret_evening_step(name_of_bar, v, next),

Saturday::DrinkABeer(next) => {

v.push((l,1));

interpret_evening_step(l, v, next(get_beer_quality_of_location(l)))

}

}

}

}

}

interpret_evening_step("Home", Vec::new(), evening)

}

Apart from the already mentioned limitation that (the luckily not too often needed) `Apply`

performs deep copies, there is another thing that has to be highlighted: The `Free`

type contains a `Box`

. This means that a complex Free Monad also has high memory complexity. This means that one should really avoid using it in performance-critical code.

If combined with continuation functions, a typical use case in eDSLs, the complexity increases even further, both memory-wise, and CPU-wise, because the continuations need to be run during interpretation.

It is also worth noting, that while building the Free Monad it's not really possible to avoid recursion. This means that building very complicated Free Monads might run into stack space limits. It's also not always predictable how deep the call stack gets if continuation functions and user-data are involved. Luckily the interpreter itself can usually be written without explicit recursions.

The next steps with this code are now to document it, and to add integration tests that also serve as examples. Once those two things are done, I'm planning to upload it to crates.io, even though it has its limitations.

Previous: Dosbox with MIDI on the Steam Deck Home Next: Upgrading from Zen 1 to Zen 3 with a B350M Mortar mainboard