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, 44 insertions, 0 deletions

diff --git a/receme/src/parapo.rs b/receme/src/parapo.rs
new file mode 100644
index 0000000..11cc613
--- /dev/null
+++ b/receme/src/parapo.rs
@@ -0,0 +1,44 @@
+//! This file defines behaviours of paramorphisms and apomorphisms.
+//!
+//! A paramorphism is a generalization of a catamorphism.  Instead of
+//! using an algebra, which is a function from F(T) to T, we use an
+//! R-algebra, which is a function from F(T, F(T)) to T.  The extra
+//! F(T) represents the contexts where the collapsing happens.
+//!
+//! An apomorphism is a generalization of anamorphism.  It is the
+//! categorical dual of a paramorphism.  So it uses an R-co-algebra,
+//! which is a function from T to F(F(T) + T), where the latter sum is
+//! the categorical co-product.
+
+use crate::{coralgebra::Coralgebra, functor::Functor, ralgebra::RAlgebra};
+
+/// A type that implements Para is capable of being collapsed to a
+/// single value by use of an R-Algebra.
+///
+/// The paramorphism consumes `self`.
+pub trait Para<T, F, R>
+where
+    F: Functor<T>,
+    R: RAlgebra<T, F>,
+{
+    /// A paramorphism takes a recursive structure and an R-algebra
+    /// for that recursive structure, and returns a single, flat,
+    /// collapsed value.
+    fn para(self, ralg: R) -> T;
+}
+
+/// A type that implements Apo is capable of being expanded from a
+/// flat value by use of an R-co-algebra.
+///
+/// The apomorphism consumes `self`.
+pub trait Apo<T, F, G, C>
+where
+    F: Functor<T>,
+    G: Functor<Result<T, F>>,
+    C: Coralgebra<T, F, G>,
+{
+    /// An apomorphism takes single, flat, collapsed value and an
+    /// R-co-algebra for a recursive structure, and returns that
+    /// recursive structure.
+    fn apo(value: T, rcoalg: C) -> Self;
+}