3
$\begingroup$

In programming languages like Rust, variables of different types that implement the same trait can have different sizes, i.e., the number of bytes used in the memory representation of the type. For example, both Map<I, F> and Filter<I, P> implement the Iterator trait but differ in size. This make it hard to implement Functor for the types implementing Iterator.

Assuming the Rust language already supports "higher-ranked types," I would like to design a Functor trait. However, attempting to implement this trait for the Iterator trait directly as shown below would not work:

trait Functor<F<_>> {
    fn map<A, B>(this: F<A>, f: impl Fn(A) -> B) -> F<B>;
}

The reason is that Iterator is a trait and not a type constructor, where Functor take a type constructor as input. Consequently, we cannot write something like Functor<Iterator>.

$\endgroup$
8
  • 2
    $\begingroup$ Hi there, welcome to the Programming Language Design and Implementation StackExchange! Currently, it seems there isn't an answerable question being asked here, as it reads as just statements. Editing your question to ask a specific question would greatly help people know how to answer your question. $\endgroup$
    – lyxal
    Aug 22, 2023 at 5:39
  • 2
    $\begingroup$ Is this about applicative functors, like in the tags, or just functors like the body? Is it about needing higher-kinded types (to express the same-container, different-contents relationship), or about varying memory allocations? Is it particularly focused on the full Rust language model, or on designing support for functional types in languages more generally? You can edit your question to be explicit about what you're looking for. $\endgroup$
    – Michael Homer
    Aug 22, 2023 at 5:47
  • 1
    $\begingroup$ What does "size" mean in this context? $\endgroup$ Aug 22, 2023 at 6:02
  • $\begingroup$ "Size" here means the number of bytes used in the type's memory representation. $\endgroup$
    – kaya3
    Aug 22, 2023 at 12:10
  • 1
    $\begingroup$ @DavidYoung pretty sure given that OP is referencing Rust it's how much memory the compiler has to allocate to hold the thing in question. I'm not sure what relevance that has to the question either. Although I don't really get the question, I'm not sure where OP got the idea that fmap can return arbitrary types. $\endgroup$ Aug 22, 2023 at 12:14

1 Answer 1

4
$\begingroup$

Rust already has a way to represent Functor using Generic Associated Types (GATs):

pub trait Functor<A> {
    type With<B>: Functor<B>;
    fn map<B>(self, f: impl Fn(A) -> B) -> Self::With<B>;
}

In this trait, Self is the functor type specialized to A, and With<B> is the functor type specialized to B (With<B> is how we emulate "higher-kinded types"). For example:

/// Dummy functor-able type
pub struct Foonctor<A>(Vec<A>, A);

impl<A> Functor<A> for Foonctor<A> {
    type With<B> = Foonctor<B>;
    fn map<B>(self, f: impl Fn(A) -> B) -> Self::With<B> {
        Foonctor(self.0.into_iter().map(&f).collect(), f(self.1))
    }
}

(playground link)

Interestingly enough, using only 2 tiny modifications, we can already make any Iterator implement Functor via blanket impl. The first modification is to add the map function's type to With, making it With<F, B>; the second modification is to make With<B> not the same type as Self but with a different parameter, but instead make it std::iter::Map<Self, F>:

/// New functor trait
pub trait Functor<A> {
    type With<F: Fn(A) -> B, B> = Functor<B>;
    fn map<F: Fn(A) -> B, B>(self, f: F) -> Self::With<F, B>;
}

/// We can still implement the new trait wherever we could implement the old one
impl<A> Functor<A> for Foonctor<A> {
    type With<F: Fn(A) -> B, B> = Foonctor<B>;
    fn map<F: Fn(A) -> B, B>(self, f: F) -> Self::With<F, B> {
        // Same exact implementation as before
        Foonctor(Iterator::map(self.0.into_iter(), &f).collect(), f(self.1))
    }
}

/// But now we can also implement it for arbitrary iterators, using std::iter::Map
impl<A, I: Iterator<Item=A>> Functor<A> for I {
    type With<F: Fn(A) -> B, B> = std::iter::Map<I, F>;
    fn map<F: Fn(A) -> B, B>(self, f: F) -> Self::With<F, B> {
        Iterator::map(self, f)
    }
}

(playground link)

However, there's one problem with the above: the functor impl for the iterator trait is a blanket impl, which prevents impls for other traits. There's a good reason for this: if Functor was blanket implemented for 2 traits, what implementation would an object which implements both traits choose? So until the specialization RFC gets accepted, this solution is non-ideal.

What we can do, though, is instead of implementing on the trait directly, use the newtype pattern and implement it on the newtype. Then you can use newtypes for other traits as well (this sidesteps the ambiguity problem because even if an object implements multiple traits, you can only choose one newtype to wrap it with and must choose one explicitly)*:

/// Trait newtype
pub struct IteratorFunctor<A, I: Iterator<Item=A>>(I);

/// Another trait newtype
pub struct FutureFunctor<A, Fut: futures::Future<Output=A>>(Fut);

/// Emulate implementing functor for a trait, by implementing on its newtype
impl<A, I: Iterator<Item=A>> Functor<A> for IteratorFunctor<A, I> {
    /// Note that we also have to wrap the `With` type with the newtype
    type With<F: Fn(A) -> B, B> = IteratorFunctor<B, std::iter::Map<I, F>>;
    fn map<F: Fn(A) -> B, B>(self, f: F) -> Self::With<F, B> {
        IteratorFunctor(self.0.map(f))
    }
}

/// Emulate implementing functor for another trait
impl<A, Fut: futures::Future<Output=A>> Functor<A> for FutureFunctor<A, Fut> {
    type With<F: Fn(A) -> B, B> = FutureFunctor<B, futures::future::Map<Fut, F>>;
    fn map<F: Fn(A) -> B, B>(self, f: F) -> Self::With<F, B> {
        use futures::future::FutureExt;
        FutureFunctor(self.0.map(f))
    }
}

/// Demo
fn main() {
    // Iterator example: [1, 2, ... 10]
    let elems = 1..=10;
    // map (* 2) elems
    let mapped_elems = IteratorFunctor(elems).map(|e| e * 2).0;
    // [2, 4, ... 20]
    println!("{:?}", mapped_elems.collect::<Vec<_>>());
    
    // Future example: { <complex calculation> = "complex calculated value" }
    let future = async {
        // Pretend we're douing some complex calculation with `.await`s here
        "complex calculated value"
    };
    // map length future
    let mapped_future = FutureFunctor(future).map(|f| f.len()).0;
    // { <complex calculation |> length> = 24 }
    println!("{:?}", futures::executor::block_on(mapped_future));
}

Here's the complete finished code (playground link)


* (In our specific example, this also makes it easier to demo actually using the trait, because Iterator::map is already defined. If we demo'd the second-last example, we'd have to explicitly call Functor::map, like how we explicitly called Iterator::map in the Foonctor impl. This isn't an issue for every blanket impl in general, it just so happens to be here, because Functor isn't the only in-scope trait which defines a method named map)

Also, for why this works even though Rust trait implementations can be different sizes: the size of std::iter::Map<I, F> is the size of whatever I it's given plus the size of F. If we call Functor::map twice we'll get IteratorFunctor<C, Map<Map<I, F0>, F1>>, 3 times and we'll get IteratorFunctor<D, Map<Map<Map<I, F0>, F1>, F2>>, etc.; all these types have different sizes, but they're all represented at compile-time and their sizes are known at compile-time.

If you're doing something where the compiler doesn't know how many times map will be called at compile time (e.g. call map in a loop): you can convert any iterator into a Box<dyn Iterator<Item=A>>, slightly modify Functor again (add a lifetime to With which bounds F), and add another newtype wrapper which returns the same type given the same type parameter:

pub trait Functor<A> {
    /// New modification: we have to add a lifetime parameter and bound `F` by it
    type With<'b, F: Fn(A) -> B + 'b, B>: Functor<B> where Self: 'b;
    fn map<'b, F: Fn(A) -> B + 'b, B>(self, f: F) -> Self::With<'b, F, B> where Self: 'b;
}

/// This wrapper doesn't contain the iterator, so we can erase the `std::iter::Map` wrappers.
/// The underlying iterator is allocated on the heap so we don't need to know its size
/// (i.e. how many times `map` was called) at compile-time
pub struct BoxIteratorFunctor<'a, A>(Box<dyn Iterator<Item=A> + 'a>);

impl<'a, A> Functor<A> for BoxIteratorFunctor<'a, A> {
    /// No `std::iter::Map` or `F` in the result type
    type With<'b, F: Fn(A) -> B + 'b, B> = BoxIteratorFunctor<'b, B> where Self: 'b;
    fn map<'b, F: Fn(A) -> B + 'b, B>(self, f: F) -> Self::With<'b, F, B> where Self: 'b {
        BoxIteratorFunctor(Box::new(self.0.map(f)))
    }
}

/// Demo
fn main() {
    // Iterator example: [1, 2, ... 10]
    let mut elems = BoxIteratorFunctor(Box::new(1u64..=10));
    for _ in 1..5 {
        // map (^ 2) elems
        // We can assign to the same variable, because it's the same type:
        //     `BoxIteratorFunctor<'static, u64>`
        elems = elems.map(move |e| e * e);
    }
    // [((((1^2)^2)^2)^2)^2, ((((2^2)^2)^2)^2)^2 ... ((((10^2)^2)^2)^2)^2]
    println!("{:?}", elems.0.collect::<Vec<_>>());
}

(playground)

$\endgroup$
3
  • $\begingroup$ Excellent job! However, I must point out that with this approach, we can't implement the Functor trait for Iterator, Future, and Option all at once... $\endgroup$
    – Jw C
    Aug 25, 2023 at 7:14
  • 1
    $\begingroup$ Not unless we wrap the Iterator and Future in newtypes to call Functor operations on them, but if we do then it's possible: play.rust-lang.org/… $\endgroup$
    – tarzh
    Aug 25, 2023 at 15:43
  • $\begingroup$ There is still one major drawback of this approach: there is no way to constraint the With<F, B> has the same type or implement the trait as the implementer. play.rust-lang.org/… $\endgroup$
    – Jw C
    Aug 27, 2023 at 8:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .