Swift Functors

Exploring the functor hierarchy in Swift for great good.

So what's the deal with functors?

Functors are a powerful abstract concept that you're already using, even if you don't already know it yet. If you're familiar with map(_:) in Array, or mapValues(_:) in Dictionary, every time you use you're using functors. You might have noticed that they share a common structure that we might like to express through a protocol, and that notion is 'a functor'.

Without getting to deep into it, a functor is an abstraction of both functions and containers. They might actually 'hold' values like an Array<Content>, or they only represent them abstractly, like (A) -> Content which doesn't 'contain' any Content directly but can spit one out whenever you give it an argument.

Some common functors are:

You'll notice that these concrete implementations are all generics, and if you've ever tried to mix protocols and generics, you'll know that there's a few things that you can't really do when mixing them.

Historically, a Functor protocol was made impossible by interactions between generics, protocols, and references to Self. For example, all generic arguments must be (fully) saturated, and the type must always be specialized, and so there is no way to refer to just Array or Dictionary sans generic arguments (although one could be tempted to fall back on using Array<Any> and the like).

If only we could figure out a way to get the compiler to accept it. Then, we could make generic functions that operate over every Functor, allowing us to map over them without knowing anything about the concrete implementation.

Well, recently Swift's type system has become powerful enough to allow a proper definition of a Functor protocol, and so we're going to do just that. We can also define and implement some other concepts that build on Functor, though they require defining things from the right perspective to get it through the type checker.

The Functor protocol

Let's start with the naive Functor protocol, which is quite simple.

protocol Functor {

    associatedtype Content

    func map<A>(_ fn: (Content) -> A) -> Self where Self.Content == A 

}

It has an associatedtype Content, which is what our functor contains. It requires the implementation of a single generic function map with one type parameter A, that takes as an argument a function (Content) -> A that turns Content into an A, and returns a copy of Self where the contents have had the function applied to it.

What makes defining this a bit tricky is the reference to Self in the return type Self where Self.Content == A. Here Self has two things that it may refer to - Self as in Self<Content>, from the instance that map is being called from, but also Self<A> as in the return value, which has had its Content type replaced. We'd really like to be able to just say that it returns Self<A>, but we're limited to using this syntax for now.

NOTE: If you allow Xcode to generate protocol stubs automatically, such as via Type 'Foo<Content>' does not conform to protocol 'Functor'. Do you want to add protocol stubs?, it will generate a stub with an incorrect type. It will generate a function map<A>(_ fn: (Content) -> A) -> Foo<Content> where A == Content, which must be fixed by changing the return type from Identity<Content> where A == Content to simply Identity<A>. Otherwise it will generate another error Same-type requirement makes generic parameters 'A' and 'Content' equivalent; this is an error in Swift 6. This may indicate that the ability to properly declare functors was unintended, though the declaration is valid.

This simple implementation of Functor allows us to write an extension for Array that makes it conform to our new protocol!

extension Array: Functor {
    
    typealias Content = Element
    
    func map<A>(_ fn: (Element) -> A) -> Array<A> {
        return self.map(fn)
    }
    
}

This is nice! However, there's a bit of a problem. This definition of functor only works for concrete collections that can immediately apply the function, but because a Functor is generic, we can't actually guarantee in general that a mapped function doesn't escape - and some functors actually require escaping functions because they map by composition.

If we build ourself a quick Fun class for wrapping functions, we can see why.

enum Fun<Argument,Result> {
    
    case fun((Argument) -> Result)

    func call(_ a: Argument) -> Result {
        switch self {
        case let .fun(this):
            return this(a)
        }
    }
    
}

If we make try and make this conform to our naive definition of Functor, we see that it fails, because Fun maps by composing it's contained function, with the new one, which causes it to escape:

extension Fun: Functor {
    
    typealias Content = Result
    
    func map<A>(_ fn: @escaping (Result) -> A) -> Fun<Argument,A> {
        switch self {
        case let .fun(this):
            return .fun({ fn(this($0)) })
        }
    }

}

We can't make Fun an instance of functor, even though it is one of the most important functors! So what can we do? We have to change Functor from being non-escaping, to allowing escaping.

protocol Functor {

    associatedtype Content

    func map<A>(_ fn: @escaping (Content) -> A) -> Self where Self.Content == A   

}

NonEscapingFunctor

This isn't just a problem for Fun, it's a problem for a lot of useful functors, such as Parser. In this case, it is better to understand that a non-escaping function is more strict than an escaping once since it has the additional guarantee of not escaping its scope. This means that we can still define a NonEscapingFunctor protocal, but it should inherit from Functor, because not every functor can guarantee non-escape, only some of them.

protocol NonEscapingFunctor: Functor {

    associatedtype Content

    func map<A>(_ fn: (Content) -> A) -> Self where Self.Content == A    
}

ThrowFunctor

Similarly, we also have a variant of functor that can throw:

public protocol ThrowFunctor: Functor {
    
    func map<A>(
        _ fn: @escaping (Content) throws -> A
    ) rethrows -> Self where Self.Content == A
    
}

This is a separate protocol from Functor for reasons similar to NonEscapingFunctor - it contains an additional capability, and requiring throws / rethrows by default would add a significant amount of noise.

Definition of NonEscapingThrowFunctor is left up to the reader.

AsyncFunctor

Furthermore, we also have a variant of functor that can map asynchronously.


public protocol AsyncFunctor: ThrowFunctor {

    func asyncMap<A>(
        _ fn: @escaping (Content) async throws -> A
    ) async rethrows -> Self where Self.Content == A

    @available(iOS 13.0, *)
    @available(macOS 10.15, *)
    func concurrentMap<A>(
        _ fn: @escaping (Content) async throws -> A
    ) async rethrows -> Self where Self.Content == A
}

Again, it is a separate protocol to avoid clutter. By now, type definitions for even single-argument functions is getting to be a tad unreadable.

Definition of NonEscapingAsyncFunctor is left up to the reader, if it is even sensible to do so.

Future work

NonEscaping, Throw, and Async aren't the only direction for extending the concept of a functor.

In the future, we'll explore: