Initial commit

Basic GNU standard files are added, and we now stop worrying about
monadic anamorphisms.

The current focus is on testing the correctness of the algorithm, so I
need convenient support for manipulating, interpreting, examining, and
per chance animating nondeterministic automata.

1 files changed, 41 insertions, 0 deletions

diff --git a/receme/src/hylo.rs b/receme/src/hylo.rs
new file mode 100644
index 0000000..8d26c19
--- /dev/null
+++ b/receme/src/hylo.rs
@@ -0,0 +1,41 @@
+//! This file defines the behaviour of hylomorphisms.
+//!
+//! A hylomorphism is a composition of an anamorphism with a
+//! catamorphism.  But it is separated into a distinct trait as we can
+//! implement hylomorphisms more efficiently by short-circuiting
+//! during the expansion by the anamorphism.
+
+use crate::{
+    algebra::Algebra,
+    catana::{Ana, Cata},
+    coalgebra::Coalgebra,
+    functor::Functor,
+};
+
+/// A type implementing Hylo is able to expand from a value of type
+/// `U` into a recursive structure holding values of type `G`, and
+/// also to collapse from that recursive structure to a value of type
+/// `T`.
+///
+/// Types which implement [`Cata`] and [`Ana`] compatibly can
+/// automatically implement [`Hylo`] as follows.
+///
+/// But of course this is not efficient, and types should implement in
+/// a more efficient manner, if available.
+///
+/// ```ignore
+/// Inter::ana(value, coalg).cata(alg)
+/// ```
+pub trait Hylo<T, S, U, F, G, H, A, C>: Cata<T, F, A> + Ana<U, H, C>
+where
+    F: Functor<T>,
+    G: Functor<S, Target<T> = F>,
+    H: Functor<U, Target<S> = G>,
+    A: Algebra<T, F>,
+    C: Coalgebra<U, H>,
+{
+    /// Expand from `value` to an intermediate recursive structure, by
+    /// means of a coalgebra, and then collapse into the result value,
+    /// by means of an algebra.
+    fn hylo(value: U, alg: A, coalg: C) -> T;
+}