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

diff --git a/receme/src/lib.rs b/receme/src/lib.rs
new file mode 100644
index 0000000..be1f028
--- /dev/null
+++ b/receme/src/lib.rs
@@ -0,0 +1,227 @@
+#![warn(missing_docs)]
+//! This crate implements some recursion schemes in Rust.
+//!
+//! The name "receme" is a mix of "Recursion Scheme".
+//!
+//! See [this series of five blog
+//! articles](https://blog.sumtypeofway.com/posts/introduction-to-recursion-schemes.html)
+//! for an introduction to recursion schemes, and see [this series of
+//! three articles](https://recursion.wtf/posts/rust_schemes/) for
+//! where I got inspired to write this library.
+//!
+//! Note that, since Rust does not have higher-kinded polymorphism, it
+//! is sometimes cumbersome to implement some notions, though.
+//!
+//! # Another crate
+//!
+//! The author of the above-mentionned three-article series has
+//! already implemented the recursion schemes in Rust, in [this
+//! repository](https://github.com/inanna-malick/recursion), so why do
+//! it myself?
+//!
+//! One reason is that I want my package to not depend on anything
+//! other than the default Rust toolchains.  This is perhaps not a
+//! very convincing reason, but I just want to do so.
+//!
+//! Another reason is that I want the design to be modular: if there
+//! is another crate that provides a similar functionality, I can
+//! quickly switch the underlying mechanism to adopt to the new crate
+//! instead.
+//!
+//! Consequently I decided to write this library, and provide a
+//! default implementation.  This way by default the package does not
+//! depend on external crates, and if so demanded, can switch to use
+//! an external crate instantaneously, at least hopefully.
+
+// The following modules are for traits.
+pub mod algebra;
+pub mod catana;
+pub mod coalgebra;
+pub mod coralgebra;
+pub mod functor;
+pub mod hylo;
+pub mod parapo;
+pub mod ralgebra;
+
+// pub mod futhis;
+
+// The following modules are for default implementations.
+pub mod tree;
+
+// TODO: benchmarks
+
+#[cfg(test)]
+mod test_expr_tree {
+    use super::{
+        catana::{Ana, Cata},
+        functor::Functor,
+        hylo::Hylo,
+        tree::{DFTree, TEStrategy, Tree, TreeIndex},
+    };
+
+    // Just for testing const generics and fixed size arrays, that is
+    // to say, just for fun.
+
+    // fn demo<T, const N: usize>(v: Vec<T>) -> Result<[T; N], String> {
+    //     v.try_into()
+    //         .map_err(|v: Vec<T>| format!("expected a vector of length {N}, but got {}", v.len()))
+    // }
+
+    // #[test]
+    // fn test_demo() -> Result<(), String> {
+    //     let v: Vec<usize> = vec![1, 2, 3];
+    //     let w: Vec<usize> = vec![1, 2];
+
+    //     assert_eq!(demo::<_, 2>(w)?, [1, 2]);
+    //     assert_eq!(demo::<_, 3>(v)?, [1, 2, 3]);
+
+    //     Ok(())
+    // }
+
+    #[derive(Debug, Clone)]
+    enum Expr<T> {
+        Add(T, T),
+        Lit(isize),
+    }
+
+    impl<T> Functor<T> for Expr<T> {
+        type Target<S> = Expr<S>;
+
+        fn fmap<S>(self, mut f: impl FnMut(T) -> S) -> Self::Target<S> {
+            match self {
+                Expr::Add(a, b) => Expr::Add(f(a), f(b)),
+                Expr::Lit(value) => Expr::Lit(value),
+            }
+        }
+    }
+
+    #[test]
+    fn test_cata() {
+        /// This is an Expr-algebra, but only for a specific type,
+        /// `isize`.
+        fn eval(expr: Expr<isize>) -> isize {
+            match expr {
+                Expr::Add(a, b) => a + b,
+                Expr::Lit(value) => value,
+            }
+        }
+
+        /// Use a temporary function to construct a tree.
+        ///
+        /// Should use an anamorphism for this purpose, later.
+        fn construct_tree() -> Tree<Expr<TreeIndex>> {
+            use Expr::{Add, Lit};
+
+            let strategy: TEStrategy = TEStrategy::UnsafeArena;
+
+            // This represents the following expression
+            //
+            // Add(1, Add(3, Add(10, -1))).
+            let elements = vec![
+                Add(1, 2).fmap(TreeIndex::new),
+                Lit(1),
+                Add(3, 4).fmap(TreeIndex::new),
+                Lit(3),
+                Add(5, 6).fmap(TreeIndex::new),
+                Lit(10),
+                Lit(-1),
+            ];
+
+            Tree::new(elements, strategy)
+        }
+
+        let tree = construct_tree();
+
+        let result = tree.cata(eval);
+
+        assert_eq!(result, 13isize);
+    }
+
+    #[test]
+    fn test_ana() {
+        // Just a ugly hack, haha.
+        let mut vector: Vec<Expr<TreeIndex>> = vec![
+            Expr::Add(1, 2).fmap(TreeIndex::new),
+            Expr::Lit(1),
+            Expr::Add(3, 4).fmap(TreeIndex::new),
+            Expr::Lit(3),
+            Expr::Add(5, 6).fmap(TreeIndex::new),
+            Expr::Lit(10),
+            Expr::Lit(-14),
+        ];
+
+        let mut vector1: Vec<Expr<TreeIndex>> = vec![
+            Expr::Add(1, 2).fmap(TreeIndex::new),
+            Expr::Lit(1),
+            Expr::Add(3, 4).fmap(TreeIndex::new),
+            Expr::Lit(3),
+            Expr::Add(5, 6).fmap(TreeIndex::new),
+            Expr::Lit(10),
+            Expr::Lit(-14),
+        ];
+
+        let mut tree = Tree::ana(TreeIndex::new(0), |value: TreeIndex| {
+            // This is safe since we visit each valid node exactly
+            // once.
+            std::mem::replace(&mut vector[*value], Expr::Lit(0))
+        });
+
+        tree.set_strategy(TEStrategy::UnsafeArena);
+
+        let tree = tree;
+
+        println!("tree is {tree:#?}");
+
+        let result = tree.cata(|expr| match expr {
+            Expr::Add(a, b) => a + b,
+            Expr::Lit(v) => v,
+        });
+
+        assert_eq!(result, 0);
+
+        // test df_tree
+        let dftree = DFTree::ana(TreeIndex::new(0), |value: TreeIndex| {
+            // This is safe since we visit each valid node exactly
+            // once.
+            std::mem::replace(&mut vector1[*value], Expr::Lit(0))
+        });
+
+        let tree = dftree.to_tree();
+
+        println!("dftree = {tree:#?}");
+
+        let result = tree.cata(|expr| match expr {
+            Expr::Add(a, b) => a + b,
+            Expr::Lit(v) => v,
+        });
+
+        assert_eq!(result, 0);
+    }
+
+    #[test]
+    fn test_hylo() {
+        // Again using the ugly hack
+        let vector: Vec<Expr<TreeIndex>> = vec![
+            Expr::Add(1, 2).fmap(TreeIndex::new),
+            Expr::Lit(1),
+            Expr::Add(3, 4).fmap(TreeIndex::new),
+            Expr::Lit(3),
+            Expr::Add(5, 6).fmap(TreeIndex::new),
+            Expr::Lit(10),
+            Expr::Lit(14),
+        ];
+
+        fn eval_expr(mut v: Vec<Expr<TreeIndex>>) -> isize {
+            Tree::hylo(
+                TreeIndex::new(0),
+                |expr| match expr {
+                    Expr::Add(a, b) => a + b,
+                    Expr::Lit(v) => v,
+                },
+                |value: TreeIndex| std::mem::replace(&mut v[*value], Expr::Lit(0)),
+            )
+        }
+
+        assert_eq!(eval_expr(vector), 28);
+    }
+}