Crate higher_free_macro
source ·Expand description
A macro that uses the traits from the higher crate and generates a Free Monad type for a given Functor.
This is a port of the Control.Monad.Free part of the “free” Haskell package by Edward Kmett.
What is a Free Monad?
A Free Monad is the left-adjoint to the Forget-Functor from the category of Monads into the category of Endofunctors.
From a programmer’s perspective, however, it is a nifty way to create a Monad, that is “based” on a given Functor
and does not impose any additional structure beyond the Monad Laws.
The structure of the Free Monad is defined by the underlying Functor.
For instance, if the underlying Functor is a Vec, the corresponding Free Monad will be a linked tree.
If the underlying Functor is an Option, the corresponding Free Monad is a linked list.
And so on, and so forth.
There are many use cases for such a data structure, the most well known one is the creation of embedded Domain Specific Languages (eDSLs). Going into detail would go beyond the scope of this documentation, however. Please check out Nikolay Yakimov’s Introduction to Free Monads for that.
There is also a blog post about the development of this macro,
that presents a simple (but inexact) mental picture
(by means of actual pictures)
of how the different Monad operations (bind, fmap, pure, apply) work on Free Monads.
How to use the macro?
For details, please see the documentation of the free macro.
In short, the syntax is either
free!(FreeMonadTypeName<'a,A>, FunctorItsBasedOn<FreeMonadTypeName<'a,A>>),
or, if the lifetime of the Free Monad depends on the lifetime of the function passed to the Functor’s fmap function,
free!(<'a>, FreeMonadTypeName<'a,A>, FunctorItsBasedOn<'a,FreeMonadTypeName<'a,A>>),
where 'a is the affected lifetime.
Examples
The project’s repository contains a folder named “examples”, which at the moment contains a tiny text adventure that shows how such a game could be implemented with Free Monads. The example highlights both, features and (current) limitations of Free Monads in Rust.
In addition, there is the “tests” folder, which contains integration tests, that show more of the syntax of the free!() macro in action.
Why a Macro?
Until non-lifetime binders become stable, this seems to be the easiest way.
In generic code, the type signature would be
enum Free<A,F> where F : Functor<Free<A,F>>.
If one now wants to implement the Functor trait for this, it is not really possible to express the
Target<T> = Free<A,F::Target<Free<A,F::Target<...>>>>
generic associated type.
See the blog post about this crate for a more detailed explanation.
A word of warning:
This crate should be considered a proof-of-concept. Its memory complexity is horrendous, and the performance of the Free Monad’s Apply
implementation can only be described as abysmal due to its reliance on deep copies.
In addition, the desugaring of do-notation currently (with higher-0.2) only works well with return types that are Copy.
If those types are big, that might be a further performance bottleneck.
There is work ongoing to add explicit clone support to higher though, so this might no longer be an issue with
later higher versions.