diff options
Diffstat (limited to 'receme/src/lib.rs')
| -rw-r--r-- | receme/src/lib.rs | 227 |
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); + } +} |