lifted 0.1.0

//! Higher-kinded types for Rust.
//!
//! This crate provides a safe higher-kinded type abstraction for use
//! in Rust programs.  The implementation is based on a suggestion by
//! Joshua Liebow-Feeser in the blog post
//! [Rust has higher kinded types already... sort of][liebow-feeser],
//! but written to be more general.  These generalizations have produced
//! largely the same scheme as described by Jeremy Yallop and Leo White
//! in [Lightweight higher-kinded polymorphism][yallop-and-white].
//!
//! - The major components.
//! - Implementing higher-kinded functionality for a type.
//! - Using higher-kinded functionality.
//! - Using the built-in higher-kinded traits.
//! - Implementation details.
//!
//! ##### The major components.
//!
//! There are three big pieces to write higher-kinded code with this
//! library:
//!
//! - Some type you wish to use in a higher-kinded way,
//! - A type representing the type constructor, implementing the type's
//!   higher-kindedness, and
//! - Code that uses the type instances constructed with the type constructor.
//!
//! The underlying implementation type can be user-defined or built-in;
//! since we're not implementing any traits on the implementation type
//! itself there are no coherence concerns limiting what types we can
//! extend this way.
//!
//! The type constructor is represented by a phantom type, one that we
//! never create an instance of.  It implements one of the `Kindn` traits,
//! depending on the kind signature.  For a one-argument implementation
//! type, such as `Option<T>` or `Vec<T>`, the type constructor would
//! implement `Kind1`.  For a two-argument implementation type, such as
//! `Result<T, E>`, the type constructor would implement `Kind2`.
//!
//! (n.b. such type constructors are provided in the `types` module, in
//! case you'd like to use these standard types in a higher-kinded way.
//! Look for `OptionC`, `VecC`, and `ResultC`.)
//!
//! To use the type instances, work with one of the `Kn` structs,
//! likewise depending on the kind signature.  In the `Option<T>` case,
//! you'd use `K1<OptionC, T>` to hold an instance.  This can be freely
//! converted back and forth between the wrapped representation and the
//! implementation type with the `new`, `inner`, `inner_mut`, and
//! `into_inner` methods.
//!
//! ##### Implementing higher-kinded functionality for a type.
//!
//! To use a type constructor in a higher-kinded way, we will create a
//! phantom type for the constructor.  For example, to start to use the
//! built-in `Vec<*>`, we create a constructor type `VecC` and specify
//! how to create the relevant result type given the type parameter.
//!
//! ```rust
//! # use lifted::Kind1;
//! /// Phantom type constructor.
//! pub struct VecC;
//!
//! impl<T> Kind1<T> for VecC {
//!     type Inner = Vec<T>;
//! }
//! ```
//!
//! Note that (roughly) this code is included in this library.
//!
//! ##### Using higher-kinded functionality.
//!
//! The main use for a higher-kinded type is to declare a kind trait
//! that various type constructors may implement.  For instance, you
//! can specify a `Functor` precisely:
//!
//! ```rust
//! # use lifted::K1;
//! pub trait Functor {
//!     fn fmap<A, B, F>(me: K1<Self, A>, f: F) -> K1<Self, B>
//!         where F: Fn(A) -> B;
//! }
//! ```
//!
//! This says that given two types, `A` and `B`, an instance of the
//! type constructor applied to `A`, and a function to map between
//! `A` and `B`, a `Functor` can produce an instance of the type
//! constructor applied to `B`.
//!
//! This kind trait could be implemented like this for the `VecC` type
//! constructor:
//!
//! ```rust
//! # use lifted::{K1, Kind1};
//! # pub struct VecC;
//! # impl<T> Kind1<T> for VecC {
//! #     type Inner = Vec<T>;
//! # }
//! # pub trait Functor {
//! #     fn fmap<A, B, F>(me: K1<Self, A>, f: F) -> K1<Self, B>
//! #         where F: Fn(A) -> B;
//! # }
//! impl Functor for VecC {
//!     fn fmap<A, B, F>(me: K1<Self, A>, f: F) -> K1<Self, B>
//!         where F: Fn(A) -> B
//!     {
//!         Self::new(              // re-wrap in helper type
//!             me.into_inner()     // unwrap helper type
//!                 .into_iter()    // vec => iter
//!                 .map(f)         // the actual map of fmap
//!                 .collect()      // iter => vec
//!         )
//!     }
//! }
//! ```
//!
//! An academic example in this library (mostly useful for unit tests)
//! includes the above `Functor` trait and `VecC` implementation.
//!
//! ##### Using the built-in higher-kinded traits.
//!
//! You might feel tempted to use the built-in higher-kinded traits as
//! some kind of Haskelly functional standard library.  Consider that
//! this might not be the best idea.  This library has its uses, but
//! rewriting everything to be based on category theory maybe isn't the
//! best thing to do.
//!
//! ##### Implementation details.
//!
//! The implementation detail most likely to be important is that the
//! data stored in a `Kn` helper struct is behind a heap allocation.
//! This allows us to store the instance in an untyped pointer and cast
//! to the appropriate instance.
//!
//! Liebow-Feeser's blog post proposes that each instance of the trait
//! handle the unsafe unwrapping, but here we encapsulate that within
//! the `Kn` helper structs.
//!
//! [liebow-feeser]: https://joshlf.com/post/2018/10/18/rust-higher-kinded-types-already/
//! [yallop-and-white]: https://www.cl.cam.ac.uk/~jdy22/papers/lightweight-higher-kinded-polymorphism.pdf

use std::marker::PhantomData;

pub mod applicative;
pub mod bifunctor;
pub mod functor;
pub mod monad;
pub mod transformer;
pub mod types;

macro_rules! impl_kind {
    (
        $( #[ $name_meta:meta ] )*
        $name:ident < $($args:ident),+ > {
            output: $output:ident,
            $( #[ $instance_meta:meta ] )*
            instance: $instance:ident,
        }
    ) => {
        $( #[ $name_meta ] )*
        pub trait $name<$($args),+> {
            /// The implementation type.  Usually (but not necessarily)
            /// parameterized on type.
            type Inner;

            /// Wrap the implementation type; see `K1::new`.
            fn new(t: $output<Self, $($args),+>) -> $instance<Self, $($args),+> {
                $instance::new(t)
            }
        }

        type $output<Me, $($args),+> = <Me as $name<$($args),+>>::Inner;

        $( #[ $instance_meta ] )*
        pub struct $instance<Me: ?Sized, $($args),+> {
            inner: *mut (),
            _me: PhantomData<Me>,
            _args: ($(PhantomData<$args>,)+),
        }

        impl<Me: ?Sized + $name<$($args),+>, $($args),+> $instance<Me, $($args),+> {
            /// Wrap an instance in the higher-kinded wrapper.
            ///
            /// ```rust
            /// # use lifted::K1;
            /// use lifted::types::OptionC;
            /// let wrapped: K1<OptionC, i32> = K1::new(None);
            /// ```
            ///
            /// There is also an alias in the `Kind1` trait which you
            /// can use to produce a wrapped type.
            ///
            /// ```rust
            /// # use lifted::{Kind1, K1};
            /// # use lifted::types::OptionC;
            /// let wrapped: K1<OptionC, i32> = OptionC::new(Some(42));
            pub fn new(t: $output<Me, $($args),+>) -> Self {
                let inner = {
                    let ptr = Box::new(t);
                    Box::into_raw(ptr) as _
                };

                $instance {
                    inner,
                    _me: PhantomData,
                    _args: ($(
                        PhantomData as PhantomData<$args>,
                    )+),
                }
            }

            /// Get a shared reference to the implementation type.
            ///
            /// ```rust
            /// # use lifted::{K1, Kind1};
            /// use lifted::types::OptionC;
            ///
            /// let nothing: K1<OptionC, i32> = OptionC::new(None);
            /// assert!(nothing.inner().is_none());
            /// ```
            pub fn inner(&self) -> &$output<Me, $($args),+> {
                unsafe {
                    &*(self.inner as *const $output<Me, $($args),+>)
                }
            }

            /// Get an exclusive reference to the implementation type.
            ///
            /// ```rust
            /// # use lifted::{K1, Kind1};
            /// use lifted::types::OptionC;
            ///
            /// let mut nothing: K1<OptionC, i32> = OptionC::new(None);
            /// *nothing.inner_mut() = Some(42);
            /// assert!(nothing.inner().is_some());
            /// ```
            pub fn inner_mut(&mut self) -> &mut $output<Me, $($args),+> {
                unsafe {
                    &mut *(self.inner as *mut $output<Me, $($args),+>)
                }
            }

            /// Extract the implementation type from the wrapper.
            ///
            /// ```rust
            /// # use lifted::{K1, Kind1};
            /// use lifted::types::OptionC;
            ///
            /// let wrapped: K1<OptionC, i32> = OptionC::new(Some(42));
            /// let unwrapped = wrapped.into_inner();
            /// assert_eq!(Some(42), unwrapped);
            /// ```
            pub fn into_inner(self) -> $output<Me, $($args),+> {
                unsafe {
                    *Box::from_raw(self.inner as *mut $output<Me, $($args),+>)
                }
            }
        }

        impl<Me: ?Sized + $name<$($args),+>, $($args),+> PartialEq for $instance<Me, $($args),+>
        where
            $output<Me, $($args),+>: PartialEq,
        {
            fn eq(&self, other: &Self) -> bool {
                self.inner() == other.inner()
            }
        }

        impl<Me: ?Sized + $name<$($args),+>, $($args),+> core::fmt::Debug for $instance<Me, $($args),+>
        where
            $output<Me, $($args),+>: core::fmt::Debug,
        {
            fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
                self.inner().fmt(f)
            }
        }

        impl<Me: ?Sized + $name<$($args),+>, $($args),+> Clone for $instance<Me, $($args),+>
        where
            $output<Me, $($args),+>: Clone,
        {
            fn clone(&self) -> Self {
                $instance::new(self.inner().clone())
            }
        }

        // TODO: all the traits in std
    }
}

impl_kind! {
    /// A type constructor of the kind `* -> *`.
    Kind1<T> {
        output: K1Type,
        /// An instance of a type produced by a unary type constructor.
        ///
        /// You can freely convert between the wrapper and implementation types
        /// with `new` and the `inner_*` methods:
        ///
        /// ```rust
        /// # use lifted::K1;
        /// use lifted::types::OptionC;
        ///
        /// let something: Option<i32> = Some(42);
        /// let mut wrapped: K1<OptionC, i32> = K1::new(something);
        ///
        /// assert!(wrapped.inner().is_some());
        ///
        /// wrapped.inner_mut().take();
        ///
        /// assert!(wrapped.into_inner().is_none());
        instance: K1,
    }
}

impl_kind! {
    /// A type constructor of the kind `* -> * -> *`.
    Kind2<T, U> {
        output: K2Type,
        /// An instance of a type produced by a binary type constructor.
        ///
        /// You can freely convert between the wrapper and implementation types
        /// with `new` and the `inner_*` methods:
        ///
        /// ```rust
        /// # use lifted::K2;
        /// use lifted::types::ResultC;
        ///
        /// let great: Result<i32, String> = Ok(42);
        /// let mut wrapped: K2<ResultC, i32, String> = K2::new(great);
        ///
        /// assert!(wrapped.inner().is_ok());
        ///
        /// *wrapped.inner_mut() = Err("does not compute".into());
        ///
        /// assert!(wrapped.into_inner().is_err());
        instance: K2,
    }
}

/// The left-applied specialization of a kind `* -> * -> *`.
pub struct K2P1_1<R: ?Sized, T> {
    _r: core::marker::PhantomData<R>,
    _t: core::marker::PhantomData<T>,
}

impl<R: Kind2<T, U>, T, U> Kind1<U> for K2P1_1<R, T> {
    type Inner = K2Type<R, T, U>;
}

/// The right-applied specialization of a kind `* -> * -> *`.
pub struct K2P1_2<R, T> {
    _r: core::marker::PhantomData<R>,
    _t: core::marker::PhantomData<T>,
}

impl<R: Kind2<T, U>, T, U> Kind1<T> for K2P1_2<R, U> {
    type Inner = K2Type<R, T, U>;
}

impl<C: Kind2<A, B>, A, B> K2<C, A, B> {
    pub fn flatten(curried: K1<K2P1_1<C, A>, B>) -> Self {
        Self::new(curried.into_inner())
    }

    pub fn unflatten(self) -> K1<K2P1_1<C, A>, B> {
        K1::new(self.into_inner())
    }
}

impl<C: Kind2<A, B>, A, B> From<K1<K2P1_1<C, A>, B>> for K2<C, A, B> {
    fn from(curried: K1<K2P1_1<C, A>, B>) -> Self {
        Self::new(curried.into_inner())
    }
}

impl<C: Kind2<A, B>, A, B> From<K2<C, A, B>> for K1<K2P1_1<C, A>, B> {
    fn from(uncurried: K2<C, A, B>) -> Self {
        Self::new(uncurried.into_inner())
    }
}

impl<C: Kind2<A, B>, A, B> From<K1<K2P1_2<C, B>, A>> for K2<C, A, B> {
    fn from(curried: K1<K2P1_2<C, B>, A>) -> Self {
        Self::new(curried.into_inner())
    }
}

impl<C: Kind2<A, B>, A, B> From<K2<C, A, B>> for K1<K2P1_2<C, B>, A> {
    fn from(uncurried: K2<C, A, B>) -> Self {
        Self::new(uncurried.into_inner())
    }
}