intermediate

Swift does not support Rank-N polymorphism yet. However, Rank-N polymorphism unlocks some interesting patterns and techniques. For this reason, Bow provides some helper classes that allow you to emulate Rank-N polymorphism. This document introduces Rank-N polymorphism and Bow’s alternative approach starting from the basics of closures.

Swift allows us to write generic functions: functions that abstract over what specific types they operate on.

```
func singletonArray<T>(_ v: T) -> [T] {
[v]
}
```

Here `singletonArray`

is a function that can operate on any type we want. Specifically, the caller of the function decides what type to pass to the function.

We say that such a function is *polymorphic* over the *type parameter* `T`

, or alternatively that the function is *generic* over the type parameter `T`

. Notice that we don’t refer to `T`

as a type. `T`

is more like a placeholder for a type that will be determined when the function is called.

Imagine we want to write a function `callTwice`

that is generic over two type parameter `A`

and `B`

and accepts our `singletonArray`

above as a parameter. Our function `callTwice`

will execute the polymorphic function we pass to it with a value of type `A`

and a second time with a value of type `B`

. We need to express that `callTwice`

takes a parameter that is a function polymorphic on a type parameter `T`

. The function could look something like this:

```
func callTwice<A, B>(_ f: <T>(T) -> [T], _ a: A, _ b: B) -> ([A], [B]) {
(f(a), f(b)) // `f` really needs to be polymorphic, because we call it twice with inputs of different types.
}
```

Notice that we included `<T>`

in front of the type signature of the parameter of our function `callTwice`

. With this, we want to express that the parameter `f`

must be a function polymorphic over one type parameter we called `T`

. This is a made up syntax, don’t try to write this in your Swift program because it won’t compile.

If we could write such a function, we could pass our `singletonArray`

function to it, along with a value of any type we want:

```
let a = callTwice(singletonArray, 0, "a") // == ([0], ["a"])
let b = callTwice(singletonArray, "b1", "b2") // == (["b1"], ["b2"])
let c = callTwice(singletonArray, "c", [0]) // == (["c"], [[0]])
```

Notice how at each call of `callTwice`

we are passing a value of different type, yet we always pass the same function `singletonArray`

which is called with each type with a value of different type. With the syntax we made up, this is possible because we are able to say that the function we pass to `callTwice`

must be a polymorphic function, in other words a function that can work with inputs of any type.

The reason we needed to use a made up syntax for this example is because Swift doesn’t allow us to write a function that requires a polymorphic function as a parameter. This feature is called *Rank-N polymorphism* and it’s supported on some languages like Haskell.

In the following sections we develop a technique to simulate Rank-N polymorphism. We start by reviewing the basics of closures. We then provide an alternative but equivalent way to encode closures that we will be able to generalise into something that approaches Rank-N polymorphism.

Swift supports higher-order functions, which means that we can pass a function as an argument to another function or return a function as the result of another function. Furthermore, we can define *closures* which are functions that capture some data from its environment.

For example, the function `randomWordGenerator`

below returns a random word of length `n`

. As you can see `n`

is a random number that is generated once each time you execute this program. `randomWordGenerator`

captures the value of `n`

, which means that the strings returned by `randomWordGenerator`

will all have the same length during the execution of the program. Each time you call `randomWordGenerator`

you will get a different word, but all of them will have the same length. If you re-run the program a second time, `n`

will probably get a different value and the length of the words returned by `randomWordGenerator`

will be different.

```
let n: Int = .random(in: 0 ..< 10)
let randomWordGenerator: () -> String = {
(0 ..< n).map { _ in
Character.random(in: "a" ... "z") |> String.init
}.joined()
}
```

In the example above we only got one `randomWordGenerator`

function per program execution: if we want a different `randomWordGenerator`

function with a different `n`

we need to re-run the program. Let’s create a function that returns a different `randomWordGenerator`

function each time we call it. This is an example of a higher-order function, since it returns another function.

```
func makeRandomWordGenerator() -> () -> String {
let length: Int = .random(in: 0 ..< 10)
return {
(0 ..< length).map { _ in
Character.random(in: "a" ... "z") |> String.init
}.joined()
}
}
```

The body of `makeRandomWordGenerator`

is basically the same code we had before (we renamed `n`

to `length`

to stress the fact that `makeRandomWordGenerator`

doesn’t use any variables from outside its body). But now, each time we call `makeRandomWordGenerator`

a different `length`

is generated, and thus we get a different `randomWordGenerator`

function each time.

We check this by creating 3 different functions with `makeRandomWordGenerator`

and generating one word with each. We should see that each function prints words of different length (unless we are a bit unlucky).

```
for _ in 0 ..< 3 {
let f = makeRandomWordGenerator()
print(f())
}
```

An important thing to realise is that we cannot just generate the random `length`

value inside the body of the closure returned from `makeRandomWordGenerator`

. If we did so, a `randomWordGenerator`

would return strings of different length each time we call it, and this is not what we want. We want each `randomWordGenerator`

function to always return strings of the same length.

This little example demonstrates that closures indeed capture values from their environment. Since we define `length`

inside `makeRandomWordGenerator`

,
there’s no way it can be accessed from outside its body. This means that the closures returned from `makeRandomWordGenerator`

indeed carry a copy of `length`

with them, because otherwise they couldn’t know what length the words they generate are supposed to be.

Now, imagine for a moment that Swift doesn’t allow closures to capture values from their environment. Now we can’t just simply pass our `randomWordGenerator`

functions around, because they cannot carry the value for `length`

they need. Is there any way we can achieve a similar behaviour?

Well, if we have our function inside a struct, it can access all the members of the struct, just like our `randomWordGenerator`

body accessed the variable `length`

.

```
struct RandomWordGenerator {
let length: Int
func callAsFunction() -> String {
(0 ..< length).map { _ in
Character.random(in: "a" ... "z") |> String.init
}.joined()
}
}
```

```
let anotherRandomWordGenerator = RandomWordGenerator(length: 6)
```

Since Swift 5.2, because we called the function in our struct `callAsFunction`

we are able to call an instance of our struct as it were a function:

```
print(anotherRandomWordGenerator())
```

And we can obviously pass a value of `RandomWordGenerator`

around, which will always hold the `length`

variable it needs. So we see that our struct behaves very much like a closure. Indeed, when the Swift compiler finds a closure definition in your code, it creates something similar to this struct under the hood.

Recall the `singletonArray`

function we defined earlier:

```
func singletonArray<T>(_ v: T) -> [T] {
[v]
}
```

Can we write this function as a struct, like we explained in the previous section? Sure thing!

```
struct SingletonArrayFunction {
func callAsFunction<T>(_ v: T) -> [T] {
[v]
}
}
```

We just expressed a polymorphic function as a struct!

Recall the function `callTwice`

we defined earlier with our made up syntax:

```
func callTwice<A, B>(_ f: <T>(T) -> [T], _ a: A, _ b: B) -> ([A], [B]) {
(f(a), f(b))
}
```

Now that we have expressed a polymorphic function as a struct, can we express this function with valid Swift syntax? Maybe something like this?

```
func callTwice<A, B>(_ f: SingletonArrayFunction, _ a: A, _ b: B) -> ([A], [B]) {
(f(a), f(b))
}
```

Well, now we can only pass a value of `SingletonArrayFunction`

, which is to say that we can only pass one specific function. This is not what we wanted, we wanted to be able to pass any polymorphic function with this signature `<T>(T) -> [T]`

. We must find another way.

`FunctionK`

is a class found in Bow that represents any polymorphic function. `FunctionK`

takes two type parameters that represent type constructors. Specifically, `FunctionK`

represents functions from `Kind<F, T>`

to `Kind<G, T>`

that is polymorphic on `T`

, or expressed with the made up notation we introduced earlier: `<T>Kind<F, T> -> Kind<G, T>`

.

Specific functions are expressed as a subclass of `FunctionK`

. Thus, if we have a function `f`

that takes a parameter of type `FunctionK<F, G>`

, we can to `f`

any function from `Kind<F, T>`

to `Kind<G, T>`

that is polymorphic. Subclasses of `FunctionK`

only need to override the generic method `invoke`

, which represents the actual body of our function. `callAsFunction`

is implemented automatically, so we can always call a `FunctionK`

as it was a regular function.

Our `SingletonArrayFunction`

defined earlier has signature (expressed in our made up syntax)`<T>(T) -> [T]`

. `[T]`

is equivalent to Bow’s `ArrayK<T>`

, i.e. `ArrayKOf<T>`

. What about the type of the input? It’s a simple type that is not wrapped with any type constructor! Worry not, we can use `IdOf<A>`

, which is a type constructor that simply wraps a value of type `A`

without adding any additional behaviour or transformation. This is to say, `IdOf<A>`

is isomorphic to `A`

we can convert a value back and forth between `IdOf<A>`

and `A`

without losing any information.

With all this in mind, we now can see that our `SingletonArrayFunction`

can be seen as a `FunctionK<ForId, ForArrayK>`

:

```
final class SingletonArrayFunction: FunctionK<ForId, ForArrayK> {
override func invoke<A>(_ fa: IdOf<A>) -> ArrayKOf<A> {
ArrayK([fa^.value])
}
}
```

Note that in order to be able to construct an array of `A`

, we need to convert from `IdOf<A>`

to `A`

by calling the property `value`

of `IdOf<A>`

. Similarly, we need to wrap the array we construct by calling the `ArrayK`

constructor.

Now we can express our `callTwice`

function with regular Swift syntax:

```
func callTwice<A, B>(_ f: FunctionK<ForId, ForArrayK>, _ a: A, _ b: B) -> ([A], [B]) {
(f(Id(a))^.asArray, f(Id(b))^.asArray)
}
```

Here we needed to perform the opposite conversion, from `A`

to `Id<A>`

by passing `a`

to the constructor of `Id`

, same for `B`

.
We also had to convert from `ArrayK<A>`

to `[A]`

by calling the property `asArray`

of `ArrayK`

.