Expressing Categories

When writing toy frameworks in my free time, they usually revolve around a category. A category is a collection of objects with arrows between them such that a) there's an identity arrow and b) arrows can be composed in an associative manner.

For instance, Swift itself is a category with types being the objects, functions being the arrows and composition being function composition. But there are a lot of other categories of interest.

Another example would be gradient based learners. There, the objects are pairs of the type of interest (e.g. images or Float-arrays) and whatever you need for backpropagation; you then compose learners by composing their forward-channel and backward-composing their backward-channel.

A third example are reducers of equal state type and equal action type. Reducers can be thought of as functions of the form (State, Action) -> State. If you have reducers of equal type, you can compose them by applying the first one and then the second one. This is an example of a monoid, i.e. a category with only one object Reducer<State, Action>.

A fourth example are views in SwiftUI. They, too, form a kind of monoid, since you can just compose views into groups. Note, however, that here the arrows are of heterogenous type, because when composing views, you don't erase them to AnyView.

Now I find myself writing a lot of boilerplate that I could erase if only I found a way to write some "category protocol" or at least an "arrow protocol". But whenever I try, I run into trouble.

protocol Arrow {
associatedtype A
associatedtype B
func compose<Other : ???>(with other: Other) -> ???
}

Any ideas?


Context: My specific use-case where I produce endless boilerplate is DI. I like the way SwiftUI handles DI, using property wrappers. However, for observed objects, this may fail if you forget to first inject an observed object. Therefore, I wanted to do it the safe way inspired by Haskell:

protocol Injector {
associatedtype Injected 
func inject(_ dependencies: MyEnvironmentType) -> Injected
}

MyEnvironmentType being essentially a wrapper for [String : Any] with a typesafe subscript. However, if you have some composition defined on the Injected types of Injectors (which can be different types!), you really do want to pull them back to your Injector types so you can just write nicer and cleaner code. It is obvious and easy to do this whenever you have a bunch of injectors injecting the same type (e.g. the reducer example): just write a monoid protocol, conform Injected to Monoid and define a composition of Injectors whenever Injected conforms to monoid. But already for improper Monoids like Views, this approach fails and you end up defining your composition for each type. This becomes a problem when you try to write not only a composition of two values, but of three, four, ..., ten values and you have to do that for anything that is composable.

2 Likes

Can you provide a concrete example involving SwiftUI views? What would compose do? Without a concrete example it will be difficult to reason about what you really want to achieve.

extension View {
@ViewBuilder
func compose<Other : View>(with other: Other) -> some View {
      self
      other
   }
}

the identity-view being the EmptyView. The composition is obviously associative, hence, Views form a category (even though Views are no functions).

Similarly, Int forms a category with + or with * as composition and 0 or 1 as identity arrow, respectively.

Given the associativity of the "arrows", you don't need to handle multiple values at once. In the specific case of View composing, you end up with a TupleView each time you compose two views:

extension View {
  func compose<Other: View>(with other: Other) -> TupleView<(Self, Other)> {
    TupleView((self, other))
  }
}

Text("Swift")
  .compose(with: Text("Scala"))
  .compose(with: Text("Haskell"))

An Arrow protocol wouldn't work with View, since View itself is a protocol. Do you intend to use Arrow only with concrete types or was it just a formalism-driven example?

Obviously writing composeall the time will work.

The reason why I want to handle multiple values at one is because imho it just looks nicer to write

Chain {
view1 //or learner1
view2 //or learner2
view3 //or learner3
}

than

view1 //or learner1
.compose(with: view2) //or learner2
.compose(with: view3) //or learner3

This is why I'm looking for a general solution so I need to write the buildBlock with 1,2,3,... arguments only once.

In order to create that Chain method independently of the number of components passed to buildBlock, you need either an homogeneous array, variadic generics or a lift over existentials based on protocols with self or associated types (PATs). Since variadic generics and unlocked PATs aren't yet available, in the case of SwiftUI Views you need to explicitly use AnyView. As I'm aware, there's no other way unfortunately.

protocol Arrow {
  static var identity: Self { get }
  func compose(with other: Self) -> Self
}

@resultBuilder
struct ComposeBuilder<Component: Arrow> {
  static func buildBlock(_ components: Component...) -> Component {
    components.reduce(.identity) { result, component in
      result.compose(with: component)
    }
  }
}

func Compose<Content: Arrow>(
  @ComposeBuilder<Content> body: () -> Content
) -> Content {
  body()
}

With AnyView you can explicitly add Arrow conformance, of course:

extension AnyView: Arrow {
  func compose(with other: AnyView) -> AnyView {
    return AnyView(TupleView((self, other)))
  }

  static var identity: AnyView { AnyView(EmptyView()) }
}

Compose {
  AnyView(Text("Swift"))
  AnyView(Text("Scala"))
  AnyView(Text("Haskell"))
}

and use Compose { ... } with any Arrow conforming type:

extension Int: Arrow {
  func compose(with other: Int) -> Int { self + other }

  static var identity: Int { 0 }
}

Compose {
  1
  2
  3
}
1 Like

That's essentially my reasoning as well. I hoped someone out there might have a proper solution in contemporary Swift that I hadn't thought of :D I mean, one can even express HKTs if one accepts that it will be bulky (Bow). With variadic generics or existentials for associatedtypes, one can make it work - at least in the instance of View which is a kind of monoid. Here's something that wouldn't even "work" (in the sense of "without boilerplate") with the above mentioned solutions:

func foo(_ arg: Int) -> String{...}
func bar(_ arg: String) -> Double?{...}
func qux(_ arg: Double?) -> Int?{...}

Chain{
foo 
bar
qux
}