summaryrefslogtreecommitdiff
path: root/receme/src
diff options
context:
space:
mode:
Diffstat (limited to 'receme/src')
-rw-r--r--receme/src/algebra.rs14
-rw-r--r--receme/src/catana.rs27
-rw-r--r--receme/src/coalgebra.rs14
-rw-r--r--receme/src/coralgebra.rs28
-rw-r--r--receme/src/functor.rs64
-rw-r--r--receme/src/hylo.rs41
-rw-r--r--receme/src/lib.rs227
-rw-r--r--receme/src/parapo.rs44
-rw-r--r--receme/src/ralgebra.rs25
-rw-r--r--receme/src/tree.rs368
10 files changed, 852 insertions, 0 deletions
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.
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-11-09 23:14:24 +0000