Yet another … yet another recursion scheme library for Haskell
Recursion schemes allow you to separate any recursion from your business logic, writing step-wise operations that can be applied in a way that guarantees termination (or, dually, progress).
How's this possible? You can’t have totality and Turing-completeness, can you? Oh, but you can – there is a particular type, Partial a
(encoded with a fixed-point) that handles potential non-termination, akin to the way that Maybe a
handles exceptional cases. It can be folded into IO
in your main function, so that the runtime can execute a Turing-complete program that was modeled totally.
yaya
– the safe operations and data types for working with recursionyaya-hedgehog
– utilities for testing your Yaya-using code with Hedgehogyaya-unsafe
– unsafe instances and operations
In the absolute, almost every change is a breaking change. This section describes how we mitigate that to provide minor updates and revisions compatible with SemVer 2.0.0.
Here are some common changes that can have unintended effects:
- adding instances can conflict with downstream orphans,
- adding a module can conflict with a module from another package,
- adding a definition to an existing module can conflict if there are unqualified imports, and
- even small bugfixes can introduce breaking changes where downstream depended on the broken results.
To mitigate some of those issues for versioning, we assume the following usage:
- modules should be imported using
PackageImports
, so that adding modules is a minor change; - modules should be imported qualified, so that adding definitions is a minor change;
- adding instances can't be mitigated in the same way, and it's not uncommon for downstream libraries to add orphans instances when they're omitted from upstream libraries. However, since these conflicts can only happen via direct dependencies, and represent an explicit downstream workaround, it’s reasonable to expect a quick downstream update to remove or conditionalize the workaround. So, this is considered a minor major change;
- deprecation is considered a revision change, however it will often be paired with minor changes.
-Werror
can cause this to fail, but published libraries shouldn't be compiled with-Werror
.
Especially if you are unfamiliar with the Haskell ecosystem, there is a Nix build (both with and without a flake). If you are unfamiliar with Nix, Nix adjacent can help you get things working in the shortest time and least effort possible.
nix build
will build and test the project fully.
nix develop
will put you into an environment where the traditional build tooling works. If you also have direnv
installed, then you should automatically be in that environment when you're in a directory in this project.
This project is built with Cabal. Individual packages will work with older versions, but ./cabal.package requires Cabal 3.6+.
Other projects similar to this one, and how they differ.
This project has been deprecated. Check out Droste instead.
Yaya is a sister library to Turtles – the same approach, but implemented in Scala. Here are some differences to be aware of:
- the
Zoo
modules in Turtles are both larger and their use is more encouraged, because Scala’s inference makes it harder to usegcata
etc. directly; - the
Unsafe
andNative
modules have different contents, because different structures are strict or lazy between the two languages. For example., in Scala,scala.collection.immutable.List
is strict, so theRecursive
instance is inNative
, while theCorecursive
instance is inUnsafe
, but Haskell’sData.List
is lazy, so theCorecursive
instance is inNative
while theRecursive
instance is inUnsafe
.
The c
type parameter specifies the arrow to use, so while it's common to
specialize to (->)
, other options can give you polymorphic recursion over
nested data types (for example., GADTs). Among other things, you can use this to define
folds of fixed-sized structures:
data VectF elem a (i :: Nat) where
EmptyVect :: VectF elem a 0
VCons :: KnownNat n => elem -> a i -> VectF elem a (n + 1)
type Vect elem n = HMu (VectF elem) n
Yaya tries to encourage you to define things in ways that are likely to maintain promises of termination. Sometimes, the compiler can even tell you when you've broken these promises, but it falls short of any guarantee of totality.
Anything known to be partial is relegated to the yaya-unsafe
package -- mostly
useful when you're in the process of converting existing directly-recursive
code.
NB: There are a number of instances (for example, Corecursive [a] (XNor a)
) that
are actually safe, but they rely on Haskell’s own recursion. We could
potentially add a module/package in between the safe and unsafe ones, containing
Corecursive
instances for types that are lazy in their recursive parameters
and Recursive
instances for ones that are strict.
We try to provide fewer fold operations (although all the usual ones can be
found in the Zoo
modules). Instead, we expect more usage of gcata
, and we
provide a collection of "algebra transformers" to make it easier to transform
various functions into generalized algebras, and between different generalized
algebras to maximize the opportunities for fusion. Although, more importantly,
it allows you to write "proto-algebras", which are functions that you expect to
use in a fold but that aren't strictly in the shape of an algebra.
Yaya has productive metamorphisms (see streamAna
and streamGApo
-- also
stream
and fstream
for more specialized versions). The naïve composition of
cata
and ana
has no benefits.
recursion-schemes combines cata
and project
into a single type
class. However, the laws for project
require either embed
or ana
, never
cata
. Similarly, the laws for cata
either stand alone or require embed
,
never project
. And you can restate this paragraph, replacing each operation
with its dual.
Also, it's impossible to define embed
for some pattern functors where it's
still possible to define project
, so project
and embed
need to be
independent.
One unfortunate consequence of the above conditions is that Projectable
is
lawless on its own. However, we expect there to be a corresponding instance of
either Corecursive
or Steppable
in all cases.
A purely ergonomic difference, yaya uses multi-parameter type classes instead of
a Base
type family.
The latter frequently requires constraints in the form of
(Recursive t, Base t ~ f)
, so we prefer Recursive t f
.
Pattern functors and algebras tend to be named independently of their
fixed-points. For example, we use Maybe
directly instead of some NatF
, XNor a b
instead of ListF
, and AndMaybe a b
instead of NonEmptyF
.
This is because many pattern functors and algebras can be applied differently in different situations, so we try to avoid pigeon-holing them and rather trying to understand what the definition itself means, rather than in the context of a fold.
I’m not as familiar with compdata, so I’ll have to look at it more before fleshing this out.
- poly-kinded recursion schemes instead of separate classes for type-indexed
recursion schemes. Using
PolyKinds
also allows for a wider variety of folds, for example, where the type index has kindType -> Type
rather than kindType
.