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

diff --git a/receme/src/functor.rs b/receme/src/functor.rs
new file mode 100644
index 0000000..95e2555
--- /dev/null
+++ b/receme/src/functor.rs
@@ -0,0 +1,64 @@
+//! This file defines the Functor trait.
+//!
+//! This is the basis of the recursion scheme.
+//!
+//! More precisely, this file provides two versions of functor traits:
+//! one whose `map` function consumes `self`, and one whose `map` does
+//! not.
+
+/// A functor can map over its generic parameter.
+///
+/// It can map from Functor(T) to Functor(S).
+pub trait Functor<T> {
+    /// The target of the map.
+    ///
+    /// Since Rust has no higher-kinded polymorphism, we have to
+    /// express this type explicitly.
+    ///
+    /// # Note
+    ///
+    /// This is a generic associated type, so we need a minimal Rust
+    /// version of 1.65, when this feature was first introduced to
+    /// stable Rust.
+    type Target<S>: Functor<S>;
+
+    /// Map from Functor(T) to Functor(S).
+    ///
+    /// # Note
+    ///
+    /// This consumes `self`.  If one wants not to consume `self`,
+    /// then consider the trait [`FunctorRef`].
+    fn fmap<S>(self, f: impl FnMut(T) -> S) -> Self::Target<S>;
+}
+
+/// A functor can map over its generic type parameter.
+///
+/// It can map from Functor(T) to Functor(S).
+///
+/// This is similar to [`Functor`], but the
+/// [`fmap`][FunctorRef<T>::fmap_ref] method takes a reference and
+/// does not consume `self`.
+pub trait FunctorRef<T> {
+    /// The target of the map.
+    ///
+    /// Since Rust has no higher-kinded polymorphism, we have to
+    /// express this type explicitly.
+    ///
+    /// # Note
+    ///
+    /// This is a generic associated type, so we need a minimal Rust
+    /// version of 1.65, when this feature was first introduced to
+    /// stable Rust.
+    type Target<S>: Functor<S>;
+
+    /// Map from Functor(T) to Functor(S).
+    ///
+    /// # Note
+    ///
+    /// This does notconsume `self`.  If one wants to consume `self`,
+    /// then consider the trait [`Functor`].
+    ///
+    /// To avoid having to specify the trait when calling the method,
+    /// we give it a distinct name.
+    fn fmap_ref<S>(&self, f: impl FnMut(T) -> S) -> Self::Target<S>;
+}