Free Category

This package contains efficient implementations of free categories. There are various representations available:

• real-time queues (C. Okasaki 'Pure Functional Data Structures')
• type aligned lists
• continuation passing style (Church encoding)

Free arrows and free Kleisli categories are also included.

Free categories are useful to model state machines in a simple yet type safe manner. For that purpose Kleisli categories are a very useful target which allows to include monadic computations. This package contains a useful generalisation of Kleisli categories captured by EffectCategory class (categories with effects), and a (free) transformer which lifts a category to a category with effects.

Benchmarks

Check performance characteristics of various representations:

• report-O0
• report-O1
• report-O2

Resources

• LoginStateMachine: based on State Machines All The Way Down by Edwin Bradly, 2017. You can run it with cabal new-run examples:login-state-machine.
• Read more here on a simple example of a finite state machine encoded using a free category using a simple GADT.
• Another example.
• Blog post on Kleisli categories.