["Request"] Simulation for derive (generic programming)

[ferranlala]

Abstract

In this issue I present a way to automatically "derive" instances of typeclasses for any algebraic data types.

Description

We need a new NaturallyIsomorphic typeclass (protocol) for higher-kinded types:

/// Indicates that this type constructor is naturally isomorphic to the `F` type constructor.
/// It is a natural isomorphism in the categorical sense only when `F` is a functor.
public protocol NaturallyIsomorphic {
    associatedtype IsomorphicTo

    static func iso<A>(_ value: Kind<IsomorphicTo, A>) -> Kind<Self, A>
    static func iso<A>(_ value: Kind<Self, A>) -> Kind<IsomorphicTo, A>
}

Higher-kinded types conforming to NaturallyIsomorphic can get instances of typeclasses from the type they are IsomorphicTo [1]. For example, if a type is NaturallyIsomorphic to a Functor then it is also a Functor.

We then need to realize that any algebraic data type is isomorphic to a canonical algebraic data type formed by nested EitherKs and PairKs (PairK is the obvious product type counterpart of EitherK[2]).

Then, we can automatically get an instance for any typeclass (that has an instance for EitherK and PairK) by only making our type NaturallyIsomorphic to some nesting of EitherKs and PairKs. We'll see an example of this equivalence below.

Sample usage

Here we define a non-trivial algebraic data type ADT. We define it directly with nested EitherKs and PairKs, so the implementation of NaturallyIsomorphic is trivial.

If we want, we can always define smart constructors or computed properties to hide the inner nesting of EitherKs and PairKs.

public final class ForADT {}
public final class ADTPartial<A, B>: Kind2<ForADT, A, B> {}
public typealias ADTOf<A, B, C> = Kind<ADTPartial<A, B>, C>

// C * (A + B * C?) = (C * A) + (C * B * C?)
public final class ADT<A, B, C>: ADTOf<A, B, C> {
    typealias IsomorphicTo = ADTPartial<A, B>.IsomorphicTo
    typealias Value = Kind<IsomorphicTo, C>

    ///  Smart constructor
    public static func c(_ c: C, andA a: A) -> ADT {
        ADT(value:
                PairK(
                    Id(c),
                    EitherK(.left(Const(a)))
                )
        )
    }

    /// Smart constructor
    public static func c(_ c: C, b: B, maybeC: Option<C>) -> ADT {
        ADT(value:
                PairK(
                    Id(c),
                    EitherK(.right(
                        PairK(
                            Const(b),
                            maybeC
                        )
                    ))
                )
        )
    }

    internal init(value: Value) {
        self.value = value
    }

    let value: Value
}

public postfix func ^ <A, B, C>(_ v: ADTOf<A, B, C>) -> ADT<A, B, C> {
    v as! ADT<A, B, C>
}

extension ADTPartial: NaturallyIsomorphic {
    // Kind<IsomorphicTo, C> = C * (A + B * C?)
    public typealias IsomorphicTo = PairKPartial<
        ForId,
        EitherKPartial<
            ConstPartial<A>,
            PairKPartial<
                ConstPartial<B>,
                OptionPartial
            >
        >
    >

    public static func iso<C>(_ value: Kind<IsomorphicTo, C>) -> ADTOf<A, B, C> {
        ADT(value: value)
    }

    public static func iso<C>(_ value: ADTOf<A, B, C>) -> Kind<IsomorphicTo, C> {
        value^.value
    }
}

extension ADTPartial: EquatableK where A: Equatable, B: Equatable {}

/// This makes ADT a functor on the type parameter A.
extension ADTPartial: Functor {}

Note how we don't need to provide implementations for EquatableK and Functor.

Passing test:

func test() {
    let v1: ADT<Bool, String, Int> = .c(1, andA: true)
    let v2: ADT<Bool, String, Int> = .c(2, b: "Hello", maybeC: nil)
    let v3: ADT<Bool, String, Int> = .c(3, b: "Hello", maybeC: .some(4))

    let v1Mapped = v1.map({ $0 + 1 })
    let v2Mapped = v2.map({ $0 + 1 })
    let v3Mapped = v3.map({ $0 + 1 })

    let v1MappedOracle: ADT<Bool, String, Int> = .c(2, andA: true)
    let v2MappedOracle: ADT<Bool, String, Int> = .c(3, b: "Hello", maybeC: nil)
    let v3MappedOracle: ADT<Bool, String, Int> = .c(4, b: "Hello", maybeC: .some(5))

    XCTAssertEqual(v1Mapped, v1MappedOracle)
    XCTAssertEqual(v2Mapped, v2MappedOracle)
    XCTAssertEqual(v3Mapped, v3MappedOracle)
}

Potential implementation

[1] NaturallyIsomorphic "inherits" instances of typeclasses from its IsomorphicTo associated type.

extension NaturallyIsomorphic {
    public static func transform<A, B>(_ f: @escaping (Kind<IsomorphicTo, A>) -> Kind<IsomorphicTo, B>)
        -> (Kind<Self, A>) -> Kind<Self, B> {

        Self.iso >>> f >>> Self.iso
    }

    /// ... and other overloads of `transform` for functions of different shape such as `(A) -> Kind<Self, B>`,
    /// omitted here fore brevity.
}

/// If a type is `NaturallyIsomorphic` to an `EquatableK` type then it is also `EquatableK`.
extension NaturallyIsomorphic where IsomorphicTo: EquatableK {
    public static func eq<A>(_ lhs: Kind<Self, A>, _ rhs: Kind<Self, A>) -> Bool where A : Equatable {
        Self.iso(lhs) == Self.iso(rhs)
    }
}

/// If a type is `NaturallyIsomorphic` to a `Functor` then it is also a `Functor`.
extension NaturallyIsomorphic where IsomorphicTo: Functor {
    public static func map<A, B>(
        _ fa: Kind<Self, A>,
        _ f: @escaping (A) -> B) -> Kind<Self, B> {
        transform(f |> flip(IsomorphicTo.map))(fa)
    }
}

[2] PairK

public final class ForPairK {}
public final class PairKPartial<F, G>: Kind2<ForPairK, F, G> {}
public typealias PairKOf<F, G, A> = Kind<PairKPartial<F, G>, A>
public final class PairK<F, G, A>: PairKOf<F, G, A> {
    public init(_ fa: Kind<F, A>, _ ga: Kind<G, A>) {
        self.run = Pair(fa, ga)
    }

    public init(run: Pair<Kind<F, A>, Kind<G, A>>) {
        self.run = run
    }

    let run: Pair<Kind<F, A>, Kind<G, A>>

    var first: Kind<F, A> {
        run.first
    }

    var second: Kind<G, A> {
        run.second
    }
}

public postfix func ^ <F, G, A>(_ fa: PairKOf<F, G, A>) -> PairK<F, G, A> {
    fa as! PairK<F, G, A>
}

extension PairKPartial: EquatableK where F: EquatableK, G: EquatableK {
    public static func eq<A>(_ lhs: PairKOf<F, G, A>, _ rhs: PairKOf<F, G, A>) -> Bool where A : Equatable {
        lhs^.first == rhs^.first && lhs^.second == rhs^.second
    }
}

extension PairKPartial: Invariant where F: Functor, G: Functor {}
extension PairKPartial: Functor where F: Functor, G: Functor {
    public static func map<A, B>(_ fa: PairKOf<F, G, A>, _ f: @escaping (A) -> B) -> PairKOf<F, G, B> {
        PairK(run: fa^.run.bimap({ F.map($0, f) }, { G.map($0, f) }))
    }
}

Modules

Bow

Breaking changes

None, new additions.

Drawbacks

I haven't tested, but I assume the performance is worse than manually written typeclass instances. Despite this, I believe the technique presented here is valuable because:

• It allows us to get typeclass instances for free when we don't care about performance
• When we care about performance, the derived instances can be used as test oracle for the manually written instances.

Proposed roadmap

1. Open PR with full PairK implementation and tests
2. Open PR with full NaturallyIsomorphic implementation and tests
3. Write documentation page describing the technique to derive typeclass instances.

Open questions

• Can optics be derived with this technique?

[ferranlala]

@truizlop let me know what you think

[truizlop]

I am glad that you are taking this further. What you are describing here is what I started in the BowGenerics module, but is incomplete. NaturallyIsomorphic would roughly correspond to the protocol Generic. The module also includes HList to avoid nested PairK when there are multiple components in a product. Likewise, we have Coproduct for multiple arities. You may want to check that out.

I would include your proposal in the BowGenerics module, except maybe the PairK which, as EitherK, can be in the main Bow module.

[ferranlala]

Oh, I didn't realise the Generic module!

Certainly, in my proposal n-products and coproducts are not supported very well, specially from the point of view of a user writing an ADT. Also, Generic allows a type to be isomorphic to any number of types, while my NaturallyIsomorphic forces you to choose one.

Do you have an example of a data type defined with the Generic module?

[ferranlala]

NaturallyIsomorphic vs Generic

Generic protocol is kind of a multi-parameter type class, but since Swift does not support that, in order for a type to "inherit" methods from its Repr, we'll need to always pass around a value of Generic, a witness of the isomorphism.
This is bad, because it's a lot of boilerplate, but it's good, because you can choose what isomorphic type you "inherit" each method from. So for example, you can "inherit" Codable methods from an isomorphic enum while inheriting Functor methods from EitherK.

With NaturallyIsomorphic, you can just call the inherited methods on your type, but you are forced to choose a single isomorphic type. However, you can always use a new type wrapper to inherit from another isomorphic type.

So, in both cases, you need some boilerplate when there's more than one isomorphic types. However, with NaturallyIsomorphic there's no boilerplate involved when there's only one isomorphic type, as opposed to Generic.

So, from that point of view, I think the approach of NaturallyIsomorphic is preferable.

Nested PairKs or EitherKs
This is something we can polish after everything else. It's a nice to have. So I'll study how to port HList, or how to merge both ideas later.