Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Emulating HKT in Swift
// This example shows how higher-kinded types can be emulated in Swift today.
// It acheives correct typing at the cost of some boilerplate, manual lifting and an existential representation.
// The technique below was directly inspired by the paper Lightweight Higher-Kinded Polymorphism
// by Jeremy Yallop and Leo White found at http://ocamllabs.io/higher/lightweight-higher-kinded-polymorphism.pdf
/// `ConstructorTag` represents a type constructor.
/// `Argument` represents an argument to the type constructor.
struct Apply<ConstructorTag, Argument> {
/// An existential containing a value of `Constructor<Argument>`
/// Where `Constructor` is the type constructor represented by `ConstructorTag`
let tag: ConstructorTag
}
/// A protocol all type constructors must conform to.
protocol TypeConstructor {
/// The existential type that erases `Argument`.
/// This should only be initializable with values of types created by the current constructor.
associatedtype Tag
/// The argument that is currently applied to the type constructor in `Self`.
associatedtype Argument
/// `self` stored in the Tag existential
var apply: Apply<Tag, Argument> { get }
/// Must unwrap the `app.tag` existential.
static func unapply(_ apply: Apply<Tag, Argument>) -> Self
}
struct ArrayTag {
fileprivate let array: Any
// Private access to the initializer is what makes this a safe technique.
// Creating an `Apply` (where the type information is stored)
// requires creating a `Tag` first.
// Using access control we can restrict that to the same file that defines
// the `Array: TypeConstructor` conformance below to ensure that
// `Apply<ArrayTag, T>` instances are only created with the correct type of
// array values.
init<T>(_ array: [T]) {
self.array = array
}
}
extension Array: TypeConstructor {
typealias Tag = ArrayTag
var apply: Apply<Tag, Element> {
return Apply<Tag, Element>(tag: ArrayTag(self))
}
static func unapply(_ apply: Apply<Tag, Element>) -> Array {
return apply.tag.array as! Array
}
}
struct OptionalTag {
fileprivate let optional: Any
init<T>(_ optional: T?) {
self.optional = optional as Any
}
}
extension Optional: TypeConstructor {
typealias Tag = OptionalTag
var apply: Apply<Tag, Wrapped> {
return Apply<Tag, Wrapped>(tag: OptionalTag(self))
}
static func unapply(_ apply: Apply<Tag, Wrapped>) -> Optional {
return apply.tag.optional as? Wrapped
}
}
protocol Monad: TypeConstructor {
static func wrap<T>(_ value: T) -> Apply<Tag, T>
func flatMap<T>(_ continuation: (Argument) -> Apply<Tag, T>) -> Apply<Tag, T>
}
extension Array: Monad {
static func wrap<T>(_ value: T) -> Apply<Tag, T> {
return [value].apply
}
func flatMap<T>(_ continuation: (Element) -> Apply<Tag, T>) -> Apply<Tag, T> {
return flatMap { [T].unapply(continuation($0)) }.apply
}
}
extension Optional: Monad {
static func wrap<T>(_ value: T) -> Apply<Tag, T> {
return (value as T?).apply
}
func flatMap<T>(_ continuation: (Wrapped) -> Apply<Tag, T>) -> Apply<Tag, T> {
return flatMap { T?.unapply(continuation($0)) }.apply
}
}
// Here we use flatMap on values of types [Int] and Int?.
// The result is automatically lifted into the corresponding emulated HKT.
// [1, 2, 3, 2, 4, 6, 3, 6, 9, 4, 8, 12]
Array.unapply([1, 2, 3, 4].flatMap { [$0, $0 * 2, $0 * 3].apply })
Optional.unapply((42 as Int?).flatMap { (($0 * 2) as Int?).apply }) // 84
Optional.unapply((nil as Int?).flatMap { _ in (nil as Int?).apply }) // nil
protocol MonadTag {
static func wrap<T>(_ value: T) -> Apply<Self, T>
static func flatMap<T, U>(_ value: Apply<Self, T>, _ continuation: (T) -> Apply<Self, U>) -> Apply<Self, U>
}
extension ArrayTag: MonadTag {
static func wrap<T>(_ value: T) -> Apply<ArrayTag, T> {
return [value].apply
}
static func flatMap<T, U>(_ value: Apply<ArrayTag, T>, _ continuation: (T) -> Apply<ArrayTag, U>) -> Apply<ArrayTag, U> {
return Array.unapply(value).flatMap(continuation)
}
}
extension OptionalTag: MonadTag {
static func wrap<T>(_ value: T) -> Apply<OptionalTag, T> {
return (value as T?).apply
}
static func flatMap<T, U>(_ value: Apply<OptionalTag, T>, _ continuation: (T) -> Apply<OptionalTag, U>) -> Apply<OptionalTag, U> {
return Optional.unapply(value).flatMap(continuation)
}
}
/// We will soon be able to declare conformances for the emulated HKT existentials themselves!
extension Apply/*: Monad */ where ConstructorTag: MonadTag {
static func wrap<T>(_ value: T) -> Apply<ConstructorTag, T> {
return ConstructorTag.wrap(value)
}
func flatMap<T>(_ continuation: (Argument) -> Apply<ConstructorTag, T>) -> Apply<ConstructorTag, T> {
return ConstructorTag.flatMap(self, continuation)
}
}
// Here we use flatMap directly on the emulated HKT values of types Apply<ArrayTag, Int>
// and Array<OptionalTag, Int> and observe the same results as flatMap applied to the base types.
// [1, 2, 3, 2, 4, 6, 3, 6, 9, 4, 8, 12]
Array.unapply([1, 2, 3, 4].apply.flatMap { [$0, $0 * 2, $0 * 3].apply })
Optional.unapply((42 as Int?).apply.flatMap { (($0 * 2) as Int?).apply }) // 84
Optional.unapply((nil as Int?).apply.flatMap { _ in (nil as Int?).apply }) // nil
protocol NaturalTransformation {
associatedtype FromTag
associatedtype ToTag
static func apply<T>(to value: Apply<FromTag, T>) -> Apply<ToTag, T>
}
// A natural transformation from T? to [t]
enum OptionalToArray: NaturalTransformation {
static func apply<T>(to optional: Apply<OptionalTag, T>) -> Apply<ArrayTag, T> {
return [Optional.unapply(optional)].flatMap { $0 }.apply
}
}
extension Apply {
func transform<Transformation: NaturalTransformation>(using transformation: Transformation.Type) -> Apply<Transformation.ToTag, Argument> where Transformation.FromTag == ConstructorTag {
return Transformation.apply(to: self)
}
}
// Apply the natural transformation to values of the emulated HKT type Apply<OptionalTag, Int>
// to receive values of emulated HKT type Apply<ArrayTag, Int> and then unwrap the result.
Array.unapply((42 as Int?).apply.transform(using: OptionalToArray.self)) // [42]
Array.unapply((nil as Int?).apply.transform(using: OptionalToArray.self)) // []
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.