coot / free-category Goto Github PK

View Code? Open in Web Editor NEW

22.0 4.0 2.0 284 KB

Free categories, free arrows and free categories with monadic actions

Home Page: https://hackage.haskell.org/package/free-category

License: Mozilla Public License 2.0

Haskell 100.00%

state-machine category free

free-category's Introduction

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:

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.

free-category's People

Contributors

Stargazers

Watchers

Forkers

turion ryno1991

free-category's Issues

Free arrows are not inspectable?

I'm new to free arrows so it's likely for me not to understand something, but why internal representation of Arr is not exposed? I'm talking about Cons constructor which remains non-exported.

My use case involves rebuilding the arrow before execution by simplifying and dropping some steps.

`Cat` has no `Arrow` instance (and friends)

This seems to be non-trivial with the current approach. It requires Arrow f => Arrow (Op f) which is not a valid implication.

Transform `Arr` to the same form as `Cat`

Measure the performance difference.

Consider free ArrowChoice

One could add a free ArrowChoice construction, similar to the free Arrow one. If you're interested, I could try that in a PR.

Add a test suite

Document how to use shell.nix

Thanks a lot for this project! It's very useful for an experiment I want to make.

I was pleasantly surprised to see a shell.nix, but it's unclear to me how to use it:

$ nix-shell
error: getting status of '/home/turion/haskell/free-category/nix/nixpkgs.nix': No such file or directory

Free Arrow in the term of Monadic Stream Function

Hi,

I am sending you a message on twitter, but I will post it anyway. So, I just watched your video on Haskell exchange. Too bad it has to end before you can show the example. I have a similar idea about free or freer arrow (though I am still at the beginner level). For the first time, I have a look into funflow's Arrow Free module.

Moreover, I like the idea of Monadic Stream Function here in

data MSF m a b = MSF { unMSF :: a -> m (b, MSF m a b) }

(further reference).

So, looking at the CPS style of A f a b,

newtype A f a b
  = A { runA :: forall r. Arrow r
             => (forall x y. f x y -> r x y)
             -> r a b
      }

is it the same result with different approach?

May I know about how you build your program with only Free Arrow? I saw that you put instance FreeAlgebra2 on the Arrow. Is it possible without the FreeAlgebra2?

Investigate `foldNatFree2` rewrite rule

Is it worth to add rewrite rules based on:

prop> foldNatFree2 nat . foldNatFree2 nat' = foldNatFree2 (foldNatFree2 nat . nat')