diff options
Diffstat (limited to 'README.md')
| -rw-r--r-- | README.md | 145 |
1 files changed, 145 insertions, 0 deletions
diff --git a/README.md b/README.md new file mode 100644 index 0000000..b23080e --- /dev/null +++ b/README.md @@ -0,0 +1,145 @@ +# 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 (and possibly wrong) port of Haskell's [Control.Monad.Free](https://hackage.haskell.org/package/free/docs/Control-Monad-Free.html) package to Rust, using the traits from [higher](https://crates.io/crates/higher). +This crate uses macros to generate a unique Free Monad type for each Functor. + +# Usage +The usage is rather straightforward. First, you create your Functor type, then call the `free!` macro to create the actual Free Monad type based on it. For example: + +```Rust +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 `Monad`, the `Functor` needs to implement `Clone`. It is needed for the `Apply` implementation, which in a Free Monad needs to call `bind()` on `self` for each `Pure` node in the other Free Monad, but `bind()`, as written in the `higher` crate, consumes `self`. The other traits (`Functor`, `Bind`, `Pure`) do not need cloneability, but without `Apply` the type is not `Applicative`, and without `Applicative` it is not `Monad`. + +# Why macros though? + This is mainly because a fully generic implementation seems impossible without [Non-lifetime Binders](https://github.com/rust-lang/rust/issues/108185), which would be needed to express the bound that the type of `Functor<A>::Result<T>` should not depend on `A`. Also, the [Never Type](https://github.com/rust-lang/rust/issues/35121) would be nice to have for a generic implementation. + + I've actually done a [proof-of-concept implementation](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=cea687f9989dd313a993facfd96adac0) of the `Functor` trait for a fully generic `Free` type using Nightly, but didn't follow this further yet, because it doesn't work in the stable toolchain yet. + + # 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): + +```Rust +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). +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 +free!(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); +} +```
\ No newline at end of file |