#![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);
    }
}