Crate algar

Algar

Algebric structures, higher-kinded types and other category theory bad ideas.

Yes, you’ll have generalized functors, applicatives, monads, traversable, free monads and much more in Rust at your fingertips. But no, they’re not as ergonomic and beautiful as in Haskell, mainly because of the lack of higher-kinded types in Rust type-system.

In the examples section you’ll also find my take on solving the expression problem in Rust: we start from a basic (wrong) implementation and then work towards a solution by trying to implement coproduct of functors and final tagless encoding.

Why?

I wrote this library for two reasons: first, mainly as a playground for learning Category Theory and Rust, second to see if it was even possible to implement such general abstract nonsense in Rust.

Does category theory make you a better programmer ?

I think it does. Category theory centers around abstraction and composition and I will argue strongly that abstraction and composition are the essence of programming.

Abstraction

Abstraction is essentially the core of computer science and exceptionally important in everyday programming: learning this sort of mathematics allows you to unlock a higher level of abstraction.

Since Category theory is the most abstract branch of math, it’s no surprise that it lends itself to great programming abstractions and then to extremely useful programming ideas. Haskell programmers have been tapping this resource for a long time, and the ideas are percolating into other languages.

Composition

All software development is composition. The act of breaking a complex problem down to smaller parts, and then composing those smaller solutions together to form structures and patterns, hence your application, well that’s what programming is all about.

We’ve been composing things forever, long before some great engineer came up with the idea of a subroutine. Some time ago the principles of structured programming revolutionized programming because they made blocks of code composable. Then came object oriented programming, which is all about composing objects. Functional programming is not only about composing functions and algebraic data structures — it makes concurrency composable — something that’s virtually impossible with other programming paradigms. – Bartosz Milewski

Interested in learning more?

I heavely recommend:

• Category Theory for Programmers
• A Pragmatic Introduction to Category Theory—Daniela Sfregola
• Functors, Applicatives, And Monads In Pictures

Walking through those resources probably won’t change your code overnight. Some people call it general abstract nonsense for a reason. That said, it does provide a nice framework for thinking about these abstract ideas, and is a recommended pursuit for all that are curious.

Prior Art

This library draws heavy inspiration from mathematics and other Rust and Elixir libraries: let me mention them here.

The Witchcraft Elixir library is why I started this journey.

The Fantasy Land Spec is a spec for projects such as this one, but targeted at Javascript. It does not come with its own implementation, but provides a helpful chart of class hierarchies.

The Scala Cats library is well documented and exceptionally enlightening on some concepts of category theory.

Fp-core.rs and higher have been invaluable resources to help me to port category theory concepts in Rust.

Obviously the Haskell Prelude deserves mention. Haskell has inspired so many programmers to write clean, declarative, functional code based on principled abstractions.

Macros

m

Provides the Haskell monadic syntactic sugar do.

Structs

ResultT

A Result (Either) transformer monad parameterized by the inner monad (M)

State

State describes a wrapped function that can be used to pass around some “hidden” pure state. This has numerous applications, but the primary advantage is purity. The state gets passed around with the value, and the monadic DSL helps it feel more natural than passing everything around by hand. Simulates a global mutable state by means of composition of pure functions. This module is inspired by the paper Functional Programming with Overloading and Higher-Order Polymorphism, Mark P Jones http://web.cecs.pdx.edu/~mpj/ Advanced School of Functional Programming, 1995.

StateT

A State transformer monad parameterized by the state type (S) and the inner monad (M)

Writer

Writer helps capture the pattern of writing to a pure log or accumulated value, handling the book-keeping for you. This is often used for loggers, but could be anything as long as the hidden value is a Monoid.

Enums

Free

A free monad is a construction which allows you to build a Monad from any Functor. Like other monads, it is a pure way to represent and manipulate computations.

Traits

Applicative

Applicative extends Apply with the ability to lift value into a particular data type or “context”.

Apply

An extension of Functor, Apply provides a way to apply arguments to functions when both are wrapped in the same kind of container. This can be seen as running function application “in a context”.

Category

A category is some collection of objects and relationships (morphisms) between them.

Foldable

A Foldable is something that can be folded over to change its structure by alter and/or combining elements to a summary value. In other words, it is a type which supports “foldr”.

Functor

The Functor trait represents the mathematical functor: a mapping between categories in the context of category theory. In practice a functor represents a type that can be mapped over.

FunctorOnce

A Functor trait where the fmap operation is a FnOnce instead of an Fn.

Monad

Monad provides a way to link actions, and a way to bring plain values into the correct context (Applicative). Monad should “derive” from Applicative and add only the bind operation, but due to the limits of the Rust type system (Higher-kinded Types are missing), we should define a dedicated trait to be able to (partially) support Monad Transformers and avoid some type madness

Monoid

In abstract algebra, a Monoid is a set equipped with an associative binary operation and an identity element. In category theory, a Monoid is a “single object category” equipped with two morphisms:

Semigroup

A Semigroup is a type with an associative operation. In plain terms, this means you can take two values of this type and add them together into a different value of the same type. The most obvious example of this is addition of numbers: 2 + 2 = 4, another is string concatenation: `“Hello “

Semigroupoid

A semigroupoid describes some way of composing morphisms on between some collection of objects.

Traversable

Traversable represents data structures which can be traversed while perserving the shape. Helpful to walk through a data structure from left to right, running some action on each element in turn. Similar to applicatives, it can be used to do things like collecting some effects