### 1 unstable release

0.1.0 | Apr 2, 2023 |
---|

#**778** in Data structures

**MPL-2.0+**

49KB

512 lines

# Disclaimer

This is a proof-of-concept. Please do not use this for production code, unless you do a careful review first. There probably are tons of bugs. Pull requests are more than welcome.

# Description

This is a simple port of parts of Haskell's Control.Monad.Free package to Rust, using the traits from higher. This crate uses macros to generate a unique Free Monad type for each user-supplied Functor.

# Usage

The usage is rather straightforward. First, you create your Functor type, then call the

macro to create the actual Free Monad type based on it. For example:`free!`

`use` `higher_free_macro``::`free`;`
`use` `higher``::``*``;`
`#``[``derive``(``Clone``,`Functor`)``]`
`enum` `TestFunctor`<A>`{`
Variant`(`A`)`
`}`
`free!``(``FreeTestFunctor``<`A`>``,` `TestFunctor``<`FreeTestFunctor`<`A`>``>``)``;`

In order to get an actual

, the `Monad`

needs to implement `Functor`

. It is needed for the `Clone`

implementation, which in a Free Monad needs to call `Apply`

on `bind``(``)`

for each `self`

node in the other Free Monad, but `Pure`

, as written in the `bind``(``)`

crate, consumes `higher`

. The other traits (`self`

, `Functor`

, `Bind`

) do not need cloneability, but without `Pure`

the type is not `Apply`

, and without `Applicative`

it is not `Applicative`

.`Monad`

If the lifetime of the result of the Functor's

depends on the lifetime of the function `fmap``(`f`)`

passed into it, the macro needs to know which lifetime parameter is affected. For instance, in the more involved example below, the macro is called as `f`

, since `free!``(``<``'a``>``,` `FreeSaturday <'a, A>`

`,`

`Saturday`

`<``'a`,FreeSaturday`<``'a`, A`>``>``)`

`;`

`Saturday`

's `fmap``(`f `:` F`)`

has `F ``:` `Fn``(`A`)``->`B `+` `'a`

.# Why macros though?

This is mainly because a fully generic implementation seems impossible without Non-lifetime Binders, which would be needed to express the bound that the type of

should not depend on `Functor <A>`

`Result`

`::`

`<`T`>``A`

. Also, the Never Type would be nice to have for a generic implementation.I've actually done a proof-of-concept implementation of a fully generic

type using Nightly, but didn't follow this further, because it doesn't work in the stable toolchain yet.`Free`

# A more involved example

The trivial example above doesn't really show much. A more involved example would for instance be building an embedded Domain Specific Language.
The code below plans a night of drinking at different bars, with varying beer quality. However, while planning we don't actually know the quality of the beer at each bar. That's a piece of information we only get while interpreting the plan (as in: that's a *side effect* of actually going there, and tasting the beer):

`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.
`}`
`//`Saturday is too complex to derive Functor for it (at the moment at least).
`//`Note that the lifetime of the continuation function for DrinkABeer depends on the lifetime of f : Fn(Next) -> B + 'a.
`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`)``)``)``)`
`}``,`
`}`
`}`
`}`
`//`Here we create the Free Monad FreeSaturday over the Functor Saturday
`//`The result of fmap(f) depends on the lifetime of f, 'a. That's why we pass this to the macro as first parameter.
`free!``(``<``'a``>``,` `FreeSaturday``<``'a`, A`>``,` `Saturday``<``'a`,FreeSaturday`<``'a`, A`>``>``)``;`
`//`Helpers, so we don't have to write FreeSaturday::lift_f() all the time
`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`)``)``)` `}`
`//`The plan for a nice evening. If someone serves lukewarm beer, we go home. Assumes that beer quality is constant at each bar.
`fn` `a_nice_evening``(``)`` ``->` `FreeSaturday``<``'static`,`(``)``>``{`
`run!` `{` `//`yes, higher has do-notation :-D
`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` `(``)` `}` `}`
`}`
`}`
`//`This wouldn't compile if a_nice_evening weren't a Monad. Sooo, it obviously is.
`fn` `_test_if_a_nice_evening_is_monad``(``)`` ``->` impl `Monad``<``'static`, `(``)``>``{`
`a_nice_evening``(``)`
`}`
`//`The interpreter that counts how many beers were consumed at which bar is a bit more convoluted than it would need to be, because:
`//`it can't match directly for box contents here, because https://github.com/rust-lang/rust/issues/87121 isn't implemented yet :-(
`//`and also cannot match for Saturday::GoToBar using pattern guards, because if-let pattern-guards aren't stable either: https://github.com/rust-lang/rust/issues/51114
`fn` `count_beers_consumed_per_bar``(``evening` `:` `FreeSaturday``<``(``)``>``)`` ``->` `Vec``<``(``&``str`, `u32``)``>``{`
`//`for this illustration let's just assume that get_beer_quality_of_location() is causing 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`)`
`}`
`//`Just to show this works. Prints [("Home", 1), ("Sunken Norwegian", 2), ("Le Rieur Sanglier", 1)].
`fn` `main``(``)`` ``{`
`let` the_free_monad `=` `a_nice_evening``(``)``;`
`let` beers_per_bar `=` `count_beers_consumed_per_bar``(`the_free_monad`)``;`
`println!``(``"``{:?}``"``,` beers_per_bar`)``;`
`}`

## An even more involved example

The "examples/text-adventure" folder in the source repo contains a (very) short text-adventure to illustrate the usage of a Free Monads as an embedded Domain Specific Language. It also shows some potential show-stoppers one should be aware of when creating a Free Monad based eDSL.

# A note about the origin of this code

The work on this project started at stillalive studios. The original goal was to learn about potential applications of Free Monads in game development, but this project has meanwhile outgrown that original plan, and has become a full proof-of-concept implementation for Free Monads in Rust, mainly developed by me (Andreas Grois) in my spare time.

# License and Copyright

Copyright (c) 2023 Andreas Grois and stillalive studios GmbH. All rights reserved.

This software is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/.

#### Dependencies

~1.5MB

~37K SLoC