Issue with Encoding HKTs Using Forward Type Declarations

Using Swift
1

I'm trying to formalise the "old school" way of encoding higher-kinded types using forward type declarations. (It's similar to how libraries like Swiftz encode HKTs.)

Given the base types TypeConstructor, TypeClass and UnaryTypeClass :

public protocol TypeConstructor {}

public protocol TypeClass {
  associatedtype F: TypeConstructor
}

public protocol UnaryTypeClass: TypeClass {
  associatedtype A
}

The unary type constructor classes Functor, Applicative and Monad:

public protocol Functor: UnaryTypeClass {
  associatedtype FB: Functor where FB.F == F

  func map <B> (_ f: (A) throws -> B) rethrows -> FB where FB.A == B
}

public protocol Applicative: Functor where FB: Applicative {
  associatedtype FA_B: Applicative where FA_B.F == F

  func apply <B> (_ ff: FA_B) -> FB where FB.A == B, FA_B.A == (A) -> B
}

public protocol Monad: Applicative where FA_B: Monad, FB: Monad {
  func flatMap (_ f: (A) throws -> FB) rethrows -> FB
}

And the implementation for Array:

public struct ArrayTypeConstructor: TypeConstructor {}

extension Array: TypeClass {
  public typealias F = ArrayTypeConstructor
}

extension Array: UnaryTypeClass {
  public typealias A = Element
}

extension Array: Functor {
  public typealias FB = [Any]
}

extension Array: Applicative {
  public typealias FA_B = [(A) -> Any]

  @inlinable public func apply <B> (_ ff: [(A) -> B]) -> [B] {
    return try! ff.flatMap(self.map)
  }
}

extension Array: Monad {}

All is well in the world of methods:

print(
  [0, 1, 2]
    .map({$0}) /* Apply the identity function. */
    .apply([{$0 + 1}]) /* Add 1. */
    .flatMap({[$0, $0]}) /* Double every element. */
)
// [1, 1, 2, 2, 3, 3]

Now we want to put our type classes to good use. Let's create a generic global map(_:_:) function that can take any Functor:

public func map <FA: Functor, B> (_ fa: FA, _ f: (FA.A) throws -> B) rethrows -> FA.FB where FA.FB.A == B {
  return try fa.map(f)
}

This compiles, but we hit a runtime error:

print(map([0, 1, 2], {$0})) // Thread 1: EXC_BAD_ACCESS (code=1, address=0x0)

The relevant stack trace:

Thread 1 Queue : com.apple.main-thread (serial)
#0	0x000000010849a897 in swift_checkMetadataState ()
#1	0x000000010844a6cd in associated type metadata accessor for Element in [A : B].Keys ()
#2	0x0000000108472cd9 in associated type metadata accessor for Element in [A] ()
#3	0x00000001081a7af9 in Collection.map<A>(_:) ()
#4	0x00000001036930fb in protocol witness for Functor.map<A>(_:) in conformance [A] ()
#5	0x00000001025d7e02 in map<A, B, C>(_:_:) at ...
...

Putting aside that the whole thing is an ugly hack, why doesn't this global function work?

(Bonus question: is there a way around it by changing the type signature somehow?)

1 Like