# 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.