Algebras is a collection type classes providing the structure for F-algebras and common operations on inductive types derived from those structures as well as a free isomorphism for converting between inductive types. Algebras values generality but not at the expense of efficency - only operations whose asymptotic complexity could not be smaller in a specific case are provided. For example the general implementation for drop
of O(n) cannot ergonomically compete with the O(1) in Data.Seq.drop
thus it is not provided; however, dropWhile
is necessarily O(n) so we can derive it from an instance of FCoalgebra
.
Algebras is suitable for use case where we care about being collection indiscriminate. For example a combinatorial parser can be implemented entirely from a FCoalgebra
. Another minor benefit is that explicit implementations of list-like operations which would typically collide are now aggergated under a single interface.
F-algebras model constructors for inductive types, so for example we can define lists as an F-algebra by
instance FAlgebra [a] where
-- The type of elements in our collection.
type FElem [a] = (a, [a])
-- ^ How we append an element to our collection.
fcons (x, xs) = x : xs
instance FCoalgebra [a] where
-- The result of a destruction.
type FCoelem [a] = Maybe (a, [a])
-- How we destruct an element of [a].
funcons [] = Nothing
funcons (x : xs) = Just (x, xs)
similar instaces exists for:
Issue and pull requests are welcome so long as the changes adhere to the guiding princples of the project mentioned in the overview. I could be convinced of extending the library with things like drop
or take
if comes packaged in a way that does not sacrifice type inference, ergonomics, or efficency but I have not found any great canidates for such a thing.
If you'd like to contribute to algebras here is a current list of ways the library could be extended.
- Add notionally distinct instances for algebras using
Reverse
to implement snoc, last, and other functions operating at the end of lists. - Add generics to automatically derive F-algebras and F-coalgebras if possible.