1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391
//! 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()) } }