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.

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.