summaryrefslogtreecommitdiff
path: root/receme/src/parapo.rs
diff options
context:
space:
mode:
authorJSDurand <mmemmew@gmail.com>2022-11-15 12:01:28 +0800
committerJSDurand <mmemmew@gmail.com>2022-11-15 12:01:28 +0800
commitcb7bcfad4ab0041aaf3fde3185e27ee46bb37788 (patch)
treea4fd99b138b72617b6c4c2b04f5d2655d0fedcc5 /receme/src/parapo.rs
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.
Diffstat (limited to 'receme/src/parapo.rs')
-rw-r--r--receme/src/parapo.rs44
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;
+}