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

//! Functors in Rust

#![warn(missing_docs)]

mod impls;
#[cfg(test)]
mod tests;

mod sealed {
    pub trait Identity<T> {}
    impl<T> Identity<T> for T {}
}

/// Trait `Identity<T>` is implemented for all `T: Sized`
/// and allows conversion between `Self` and `T`
pub trait Identity<T>: Sized + sealed::Identity<T> {
    /// Convert from `T` into `Self` (no-op)
    fn from_same(this: T) -> Self;
    /// Convert from `Self` into `T` (no-op)
    fn into_same(self) -> T;
}

impl<T> Identity<T> for T
where
    T: sealed::Identity<T>,
{
    fn from_same(this: T) -> Self {
        this
    }
    fn into_same(self) -> T {
        self
    }
}

/// A generic type (e.g. `Vec<A>`) whose inner type can be mapped over
/// (e.g. to `Vec<B>`)
///
/// Type parameter `B` specifies the new inner type after the [`fmap`]
/// operation.
///
/// [`fmap`]: Self::fmap
pub trait Functor<'a, B>
where
    Self: Identity<Self::Mapped<'a, Self::Inner>>,
    B: 'a,
{
    /// Inner type (e.g. `Inner = A` for `Vec<A>`)
    type Inner: 'a;

    /// `Self` with inner type mapped to a different type
    ///
    /// For example,
    /// `<Vec<A> as Functor<'a, B>>::Mapped<'b, C> = Vec<C>`.
    /// It is required that `T::Mapped<'a, T::Inner> = T` (which is
    /// ensured by the compiler).
    type Mapped<'b, C>
    where
        'a: 'b,
        C: 'a;

    /// Replaces inner type and value by applying a mapping function
    fn fmap<'b, F>(self, f: F) -> Self::Mapped<'b, B>
    where
        'a: 'b,
        F: 'b + Fn(Self::Inner) -> B;

    /// Specialized variant of [`fmap`] where the [inner type] isn't
    /// changed
    ///
    /// Opposed to [`fmap`], this method returns `Self` instead of
    /// [`Self::Mapped<B>`], which can help reducing unnecessary trait
    /// bounds.
    /// Its default implementation may be overriden where a more
    /// efficient implementation is available when [`Functor<B>::Inner`]
    /// and `B` are the same types.
    ///
    /// [`fmap`]: Functor::fmap
    /// [inner type]: Self::Inner
    fn fmap_same<F>(self, f: F) -> Self
    where
        Self: FunctorSelf<'a, B>,
        F: 'a + Fn(Self::Inner) -> Self::Inner,
    {
        self.fmap_same_default_impl(f)
    }
}

/// Helper trait to convert between [`<T as Functor>::Mapped`] and `T`
///
/// [`<T as Functor>::Mapped`]: Functor::Mapped
pub trait FunctorSelf<'a, A>: Functor<'a, A>
where
    A: 'a,
{
    /// Convert from [`Functor::Mapped<A>`] into `Self` (no-op)
    fn from_mapped(x: Self::Mapped<'a, A>) -> Self;
    /// Convert from [`Self`] into [`Functor::Mapped<A>`] (no-op)
    fn into_mapped(self) -> Self::Mapped<'a, A>;
    /// Wrapper around [`Functor::fmap`], which converts the return
    /// value into `Self` (no-op conversion)
    ///
    /// This method is the default implementation for
    /// [`Functor::fmap_same`], which may be overridden when
    /// implementing the [`Functor`] trait.
    fn fmap_same_default_impl<F>(self, f: F) -> Self
    where
        F: 'a + Fn(Self::Inner) -> Self::Inner;
}

impl<'a, T, A> FunctorSelf<'a, A> for T
where
    A: 'a,
    T: Functor<'a, A, Inner = A>,
{
    fn from_mapped(mapped: Self::Mapped<'a, A>) -> Self {
        Self::from_same(mapped)
    }
    fn into_mapped(self) -> Self::Mapped<'a, A> {
        self.into_same()
    }
    fn fmap_same_default_impl<F>(self, f: F) -> Self
    where
        F: 'a + Fn(A) -> A,
    {
        Self::from_mapped(self.fmap(f))
    }
}