ordofp_core 0.1.0

OrdoFP core provides developers with HList, Disiunctio, NominataUniversalis, Universalis, and functional type classes
Documentation 
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

//! Core traits for recursion schemes.
//!
//! > *"Forma dat esse rei."*
//! > — Form gives being to a thing. (Aquinas)

#[cfg(feature = "alloc")]
use alloc::boxed::Box;

use crate::typeclasses::hkt::{FunctorHKT, HKT};

/// The base functor type family.
///
/// Every recursive type has an associated "base functor" that represents
/// one layer of the recursive structure with the recursion replaced by
/// a type parameter.
///
/// # Example
///
/// For a recursive list type `List<A>`, the base functor would be:
///
/// ```rust
/// enum ListF<A, R> {
///     Nil,
///     Cons(A, R),
/// }
///
/// let layer: ListF<i32, ()> = ListF::Cons(42, ());
/// match layer {
///     ListF::Cons(x, ()) => assert_eq!(x, 42),
///     ListF::Nil => panic!("expected Cons"),
/// }
/// ```
///
/// Where `R` is the recursion variable.
pub trait FunctorBasis {
    /// The base functor type.
    /// `F` is a type that implements `FunctorHKT`.
    type Base: FunctorHKT;
}

/// Recursiva - Trait for types that can be recursively folded.
///
/// > *"Descensus ab universali ad particulare."*
/// > — Descent from the universal to the particular.
///
/// A type is `Recursiva` if we can project it into its base functor
/// applied to itself. This enables catamorphisms (folds).
///
/// # Laws
///
/// For any `Recursiva` type with `embed` as its inverse:
///
/// ```text
/// embed(project(t)) == t  // embed-project identity
/// ```
#[cfg(feature = "alloc")]
pub trait Recursiva: FunctorBasis + Sized {
    /// Project one layer of recursion.
    ///
    /// Takes a recursive structure and exposes one layer,
    /// with recursive positions containing the original type.
    fn project(self) -> <Self::Base as HKT>::Target<Self>;
}

/// Corecursiva - Trait for types that can be recursively unfolded.
///
/// > *"Ascensus a particulari ad universale."*
/// > — Ascent from the particular to the universal.
///
/// A type is `Corecursiva` if we can embed its base functor
/// applied to itself back into the type. This enables anamorphisms (unfolds).
///
/// # Laws
///
/// For any `Corecursiva` type with `project` as its inverse:
///
/// ```text
/// project(embed(f)) == f  // project-embed identity
/// ```
#[cfg(feature = "alloc")]
pub trait Corecursiva: FunctorBasis + Sized {
    /// Embed one layer of base functor.
    ///
    /// Takes a layer of the base functor with recursive positions
    /// and wraps it into the recursive type.
    fn embed(layer: <Self::Base as HKT>::Target<Self>) -> Self;
}

/// Birecursiva - Trait for types that are both recursive and corecursive.
///
/// > *"Idem est principium et finis."*
/// > — The beginning and the end are the same.
///
/// Most useful recursive data types implement both traits.
#[cfg(feature = "alloc")]
pub trait Birecursiva: Recursiva + Corecursiva {}

#[cfg(feature = "alloc")]
impl<T: Recursiva + Corecursiva> Birecursiva for T {}

// =============================================================================
// Fix Implementation
// =============================================================================

#[cfg(feature = "alloc")]
use crate::fix::Fix;

#[cfg(feature = "alloc")]
impl<F: FunctorHKT> FunctorBasis for Fix<F> {
    type Base = F;
}

#[cfg(feature = "alloc")]
impl<F: FunctorHKT> Recursiva for Fix<F> {
    #[inline]
    fn project(self) -> F::Target<Self> {
        *self.0
    }
}

#[cfg(feature = "alloc")]
impl<F: FunctorHKT> Corecursiva for Fix<F> {
    #[inline]
    fn embed(layer: F::Target<Self>) -> Self {
        Fix(Box::new(layer))
    }
}