diff options
Diffstat (limited to 'receme')
| -rw-r--r-- | receme/Cargo.toml | 9 | ||||
| -rw-r--r-- | receme/src/algebra.rs | 14 | ||||
| -rw-r--r-- | receme/src/catana.rs | 27 | ||||
| -rw-r--r-- | receme/src/coalgebra.rs | 14 | ||||
| -rw-r--r-- | receme/src/coralgebra.rs | 28 | ||||
| -rw-r--r-- | receme/src/functor.rs | 64 | ||||
| -rw-r--r-- | receme/src/hylo.rs | 41 | ||||
| -rw-r--r-- | receme/src/lib.rs | 227 | ||||
| -rw-r--r-- | receme/src/parapo.rs | 44 | ||||
| -rw-r--r-- | receme/src/ralgebra.rs | 25 | ||||
| -rw-r--r-- | receme/src/tree.rs | 368 |
11 files changed, 861 insertions, 0 deletions
diff --git a/receme/Cargo.toml b/receme/Cargo.toml new file mode 100644 index 0000000..dccf28c --- /dev/null +++ b/receme/Cargo.toml @@ -0,0 +1,9 @@ +[package] +name = "receme" +version = "0.1.0" +edition = "2021" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] + diff --git a/receme/src/algebra.rs b/receme/src/algebra.rs new file mode 100644 index 0000000..49e0932 --- /dev/null +++ b/receme/src/algebra.rs @@ -0,0 +1,14 @@ +//! This file defines the algebra trait. +//! +//! If F is an endo-functor, then an F-algebra is a natural +//! transformation from F to the identity functor. + +use super::functor::Functor; + +/// An algebra is a function from F(T) to T. +/// +/// This is a "trait alias". Since Rust does not support trait alias +/// yet, we define an empty trait with an automatic implementation. +pub trait Algebra<T, F: Functor<T>>: FnMut(F) -> T {} + +impl<T, F: Functor<T>, A: FnMut(F) -> T> Algebra<T, F> for A {} diff --git a/receme/src/catana.rs b/receme/src/catana.rs new file mode 100644 index 0000000..e3d4728 --- /dev/null +++ b/receme/src/catana.rs @@ -0,0 +1,27 @@ +//! This file defines behaviours of catamorphisms and anamorphisms. +//! +//! A catamorphism collapses a recursive structure into a flat value, +//! whereas an anamorphism expands a value into a recursive structure. + +use crate::{algebra::Algebra, coalgebra::Coalgebra, functor::Functor}; + +/// A type that implements Cata is capable of being collapsed into a single value. +/// +/// The catamorphism consumes `self`. +pub trait Cata<T, F: Functor<T>, A: Algebra<T, F>> { + /// A catamorphism takes a recursive structure and an algebra for + /// the recursive structure, and returns a single, flat, collapsed + /// value. + fn cata(self, alg: A) -> T; +} + +/// A type that implements Ana is capable of being expanded from a +/// flat value. +/// +/// The anamorphism consumes `self`. +pub trait Ana<T, F: Functor<T>, C: Coalgebra<T, F>> { + /// An anamorphism takes a single, flat, collapsed value and a + /// co-algebra for a recursive structure, and returns that + /// recursive structure. + fn ana(value: T, coalg: C) -> Self; +} diff --git a/receme/src/coalgebra.rs b/receme/src/coalgebra.rs new file mode 100644 index 0000000..5974d90 --- /dev/null +++ b/receme/src/coalgebra.rs @@ -0,0 +1,14 @@ +//! This file defines the co-algebra trait. +//! +//! If F is an endo-functor, then an F-co-algebra is a natural +//! transformation from the identity functor to F. + +use super::functor::Functor; + +/// A co-algebra is a function from T to F(T). +/// +/// This is a "trait alias". Since Rust does not support trait alias +/// yet, we define an empty trait with an automatic implementation. +pub trait Coalgebra<T, F: Functor<T>>: FnMut(T) -> F {} + +impl<T, F: Functor<T>, C: FnMut(T) -> F> Coalgebra<T, F> for C {} diff --git a/receme/src/coralgebra.rs b/receme/src/coralgebra.rs new file mode 100644 index 0000000..a4a73d2 --- /dev/null +++ b/receme/src/coralgebra.rs @@ -0,0 +1,28 @@ +//! This file defines the behaviours of R-co-algebras. +//! +//! For a functor F, an R-co-algebra is a natural transformation from +//! the identity functor to F1, where F1 is the functor that sends T +//! to F(F(T) + T), where the + is the categorical co-product, +//! represented in Rust as `Result`. And the F(T) variant means to +//! short-circuit the expansion. + +use crate::functor::Functor; + +/// An R-co-algebra is a function from T to F(Result<F(T), T>). +/// +/// This is a "trait alias". Since Rust does not support trait alias +/// yet, we define an empty trait with an automatic implementation. +pub trait Coralgebra<T, F, G>: FnMut(T) -> G +where + F: Functor<T>, + G: Functor<Result<T, F>>, +{ +} + +impl<T, F, G, R> Coralgebra<T, F, G> for R +where + F: Functor<T>, + G: Functor<Result<T, F>>, + R: FnMut(T) -> G, +{ +} 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>; +} diff --git a/receme/src/hylo.rs b/receme/src/hylo.rs new file mode 100644 index 0000000..8d26c19 --- /dev/null +++ b/receme/src/hylo.rs @@ -0,0 +1,41 @@ +//! This file defines the behaviour of hylomorphisms. +//! +//! A hylomorphism is a composition of an anamorphism with a +//! catamorphism. But it is separated into a distinct trait as we can +//! implement hylomorphisms more efficiently by short-circuiting +//! during the expansion by the anamorphism. + +use crate::{ + algebra::Algebra, + catana::{Ana, Cata}, + coalgebra::Coalgebra, + functor::Functor, +}; + +/// A type implementing Hylo is able to expand from a value of type +/// `U` into a recursive structure holding values of type `G`, and +/// also to collapse from that recursive structure to a value of type +/// `T`. +/// +/// Types which implement [`Cata`] and [`Ana`] compatibly can +/// automatically implement [`Hylo`] as follows. +/// +/// But of course this is not efficient, and types should implement in +/// a more efficient manner, if available. +/// +/// ```ignore +/// Inter::ana(value, coalg).cata(alg) +/// ``` +pub trait Hylo<T, S, U, F, G, H, A, C>: Cata<T, F, A> + Ana<U, H, C> +where + F: Functor<T>, + G: Functor<S, Target<T> = F>, + H: Functor<U, Target<S> = G>, + A: Algebra<T, F>, + C: Coalgebra<U, H>, +{ + /// Expand from `value` to an intermediate recursive structure, by + /// means of a coalgebra, and then collapse into the result value, + /// by means of an algebra. + fn hylo(value: U, alg: A, coalg: C) -> T; +} 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); + } +} 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; +} diff --git a/receme/src/ralgebra.rs b/receme/src/ralgebra.rs new file mode 100644 index 0000000..989089e --- /dev/null +++ b/receme/src/ralgebra.rs @@ -0,0 +1,25 @@ +//! This file defines the behaviours of R-algebras. +//! +//! For a functor F, an R-algebra is a natural transformation from F1 +//! to the identity functor, where F1 is the functor that sends T to +//! F((F(T), T)). This extra F(T) represents the context during the +//! computations. + +use crate::functor::Functor; + +/// An R-algebra is a function from F((F(T), T)) to T. +/// +/// This is a "trait alias". Since Rust does not support trait alias +/// yet, we define an empty trait with an automatic implementation. +pub trait RAlgebra<T, F>: FnMut((T, F)) -> T +where + F: Functor<T>, +{ +} + +impl<T, F, R> RAlgebra<T, F> for R +where + F: Functor<T>, + R: FnMut((T, F)) -> T, +{ +} diff --git a/receme/src/tree.rs b/receme/src/tree.rs new file mode 100644 index 0000000..eb64f31 --- /dev/null +++ b/receme/src/tree.rs @@ -0,0 +1,368 @@ +//! This file implements a recursive structure that implements the +//! recursion scheme traits, representing trees. +//! +//! The tree is backed by a vector. + +use crate::{ + algebra::Algebra, + catana::{Ana, Cata}, + coalgebra::Coalgebra, + functor::Functor, + hylo::Hylo, +}; + +use std::{collections::VecDeque, mem::MaybeUninit, ops::Deref}; + +/// The evaluation strategy for the tree. +#[derive(Default, Debug, Copy, Clone)] +pub enum TEStrategy { + #[default] + /// This strategy uses an arena, and uses an `Option<T>` to store + /// the data. + /// + /// # Comparison: + /// + /// Since it is an arena, it saves allocations, compared to the + /// variant [`DepthFirst`][TEStrategy::DepthFirst]. But it needs + /// indices to operate, so uses more memory. + /// + /// On the other hand, it uses an option, so is slower than the + /// variant [`UnsafeArena`][TEStrategy::UnsafeArena], but avoids + /// unsafe code altogether. Applications can first use this + /// variant to make sure the algorithm works, before converting to + /// use the unsafe variant. + SafeArena, + /// This strategy uses an arena, and uses an `MaybeUninit` to + /// store the data. + /// + /// # Comparison: + /// + /// Since it is an arena, it saves allocations, compared to the + /// variant [`DepthFirst`][TEStrategy::DepthFirst]. But it needs + /// indices to operate, so uses more memory. + /// + /// On the other hand, it uses a `MaybeUninit`, so is faster than + /// the variant [`SafeArena`][TEStrategy::SafeArena], but uses + /// unsafe code. Applications can first use the safe variant to + /// make sure the algorithm works, before converting to use this + /// variant. + UnsafeArena, + /// This strategy uses a plain vector. + /// + /// # Comparison: + /// + /// Since it is a plain vector, it uses more allocations, compared + /// to other variants. But it does not use indices, so consumes + /// less memory. + /// + /// # Warning + /// + /// Since it uses no indices, it relies on the depth-first order + /// of the elements to correctly find elements. This puts a + /// requirement on the implementation of the [`Functor`] trait. + DepthFirst, +} + +/// A tree is just a wrapper around a vector. +/// +/// # Warning +/// +/// The tree is supposed to be stored in topological order. This +/// order is used in a critical way in the implementations of +/// recursion schemes. Violations of this assumption are fatal to +/// using those trait methods. +#[derive(Clone, Debug)] +pub struct Tree<T> { + elements: Vec<T>, + strategy: TEStrategy, +} + +impl<T> Tree<T> { + #[inline] + /// Construct a new tree. + pub fn new(elements: Vec<T>, strategy: TEStrategy) -> Self { + Self { elements, strategy } + } + + /// Just a function for testing. + /// + /// # Warning + /// + /// This is definitely going to be removed in the future. + pub fn nth(&self, n: usize) -> Option<&T> { + self.elements.get(n) + } + + #[inline] + /// Retrieve the strategy of the tree. + pub fn strategy(&self) -> TEStrategy { + self.strategy + } + + #[inline] + /// Set the strategy of the tree. + pub fn set_strategy(&mut self, strategy: TEStrategy) { + self.strategy = strategy; + } +} + +// Manual implementation can avoid unnecessary requirement on the +// parameter `T`. +impl<T> Default for Tree<T> { + fn default() -> Self { + let elements = Vec::new(); + let strategy = TEStrategy::default(); + + Self { elements, strategy } + } +} + +#[derive(Debug, Copy, Clone)] +/// A thin wrapper around `usize`, to index vectors. +/// +/// By means of the [*newtype +/// pattern*](https://doc.rust-lang.org/rust-by-example/generics/new_types.html) +/// in Rust, it is supposed to be treated as a simple `usize` in the +/// compiled codes. +pub struct TreeIndex(usize); + +impl TreeIndex { + /// Wrap an index in this type. + pub fn new(index: usize) -> Self { + Self(index) + } +} + +impl Deref for TreeIndex { + type Target = usize; + + fn deref(&self) -> &Self::Target { + &self.0 + } +} + +impl<T, F, G, A> Cata<T, F, A> for Tree<G> +where + F: Functor<T>, + G: Functor<TreeIndex, Target<T> = F>, + A: Algebra<T, F>, +{ + fn cata(self, mut alg: A) -> T { + // First deal with the safe case + match self.strategy { + TEStrategy::SafeArena => { + let mut results: Vec<Option<T>> = std::iter::repeat_with(Default::default) + .take(self.elements.len()) + .collect(); + + for (index, node) in self.elements.into_iter().enumerate().rev() { + let algebra_result = { + let node = node.fmap::<T>(|index| { + std::mem::replace(&mut results[*index], None).unwrap() + }); + + alg(node) + }; + + // Artificially use this value to satisfy the compiler. + let _ = std::mem::replace(&mut results[index], Some(algebra_result)); + } + + std::mem::replace(&mut results[0], None).unwrap() + } + TEStrategy::UnsafeArena => { + let mut results: Vec<MaybeUninit<T>> = std::iter::repeat_with(MaybeUninit::uninit) + .take(self.elements.len()) + .collect(); + + for (index, node) in self.elements.into_iter().enumerate().rev() { + let algebra_result = { + let node = node.fmap::<T>(|index| unsafe { + std::mem::replace(&mut results[*index], MaybeUninit::uninit()) + .assume_init() + }); + + alg(node) + }; + + results[index].write(algebra_result); + } + + unsafe { std::mem::replace(&mut results[0], MaybeUninit::uninit()).assume_init() } + } + TEStrategy::DepthFirst => { + let mut results_stack: Vec<T> = Vec::new(); + + for node in self.elements.into_iter().rev() { + // Replace each node data with the value from the + // results stack. + let mapped_node = node.fmap(|_| results_stack.pop().unwrap()); + + results_stack.push(alg(mapped_node)); + } + + results_stack.pop().unwrap() + } + } + } +} + +impl<T, F, G, C> Ana<T, F, C> for Tree<G> +where + F: Functor<T, Target<TreeIndex> = G>, + G: Functor<TreeIndex>, + C: Coalgebra<T, F>, +{ + /// An anamorphism takes a single, flat, collapsed value and a + /// co-algebra for a recursive structure, and returns that + /// recursive structure. + /// + /// # Descriptions + /// + /// This always generates a tree which uses the default strategy. + /// If one wants to use a different strategy, set the strategy + /// after generating the tree. + /// + /// # See also + /// + /// To use the depth first strategy to generate the tree, use the + /// wrapper struct [`DFTree`]. + fn ana(value: T, mut coalg: C) -> Self { + let mut queue = VecDeque::new(); + + queue.push_back(value); + + let mut elements = vec![]; + + let strategy = TEStrategy::default(); + + while let Some(value) = queue.pop_back() { + let expanded_layer = coalg(value); + + let mapped_layer = expanded_layer.fmap::<TreeIndex>(|value| { + queue.push_back(value); + + TreeIndex(elements.len() + queue.len()) + }); + + elements.push(mapped_layer); + } + + Self { elements, strategy } + } +} + +/// To generate a tree with the strategy +/// [`DepthFirst`][TEStrategy::DepthFirst], we use a wrapper struct +/// which implements [`Ana`] in the desired manner. +#[derive(Debug, Clone)] +pub struct DFTree<T>(Tree<T>); + +impl<T> DFTree<T> { + #[inline] + /// Convert to the underlying tree. + pub fn to_tree(self) -> Tree<T> { + self.0 + } + + #[inline] + /// Wrap a tree. + pub fn new(tree: Tree<T>) -> Self { + Self(tree) + } +} + +impl<T, F, G, C> Ana<T, F, C> for DFTree<G> +where + F: Functor<T, Target<TreeIndex> = G>, + G: Functor<TreeIndex>, + C: Coalgebra<T, F>, +{ + /// An anamorphism takes a single, flat, collapsed value and a + /// co-algebra for a recursive structure, and returns that + /// recursive structure. + /// + /// # Descriptions + /// + /// This always generates a tree which uses the depth first + /// strategy. If one wants to use a different strategy, set the + /// strategy after generating the tree. + /// + /// # See also + /// + /// To use the default strategy to generate the tree, use the + /// original struct [`Tree`]. + fn ana(value: T, mut coalg: C) -> Self { + let mut stack = Vec::new(); + + stack.push(value); + + let mut elements = vec![]; + + let strategy = TEStrategy::DepthFirst; + + while let Some(value) = stack.pop() { + let expanded_layer = coalg(value); + + let mut local_stack = Vec::new(); + + let mapped_layer = expanded_layer.fmap::<TreeIndex>(|value| { + local_stack.push(value); + + // The index is of no meaning here, since we rely on + // the depth-first order. + TreeIndex(0) + }); + + stack.extend(local_stack.into_iter().rev()); + + elements.push(mapped_layer); + } + + Self::new(Tree::new(elements, strategy)) + } +} + +impl<T, U, F, G, H, A, C> Hylo<T, TreeIndex, U, F, G, H, A, C> for Tree<G> +where + F: Functor<T>, + G: Functor<TreeIndex, Target<T> = F>, + H: Functor<U, Target<TreeIndex> = G>, + A: Algebra<T, F>, + C: Coalgebra<U, H>, +{ + fn hylo(value: U, mut alg: A, mut coalg: C) -> T { + // The hylomorphism ignores the tree. Maybe I will add + // different implementations later on. + + let mut result_stack: Vec<T> = Vec::new(); + let mut value_node_stack: Vec<Result<U, G>> = vec![Ok(value)]; + + while let Some(value_or_node) = value_node_stack.pop() { + match value_or_node { + Ok(value) => { + let node = coalg(value); + + let mut local_values: Vec<U> = Vec::new(); + + let mapped_node = node.fmap(|node_value| { + local_values.push(node_value); + TreeIndex::new(0) + }); + + value_node_stack.push(Err(mapped_node)); + value_node_stack.extend(local_values.into_iter().rev().map(Ok)); + } + Err(node) => { + let mapped_node = node.fmap(|_| result_stack.pop().unwrap()); + + result_stack.push(alg(mapped_node)); + } + } + } + + result_stack.pop().unwrap() + } +} + +// TODO: Para, Apo, Histo, and Futu await us. |