summaryrefslogtreecommitdiff
path: root/receme/src/lib.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/lib.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/lib.rs')
-rw-r--r--receme/src/lib.rs227
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);
+ }
+}