Exploring the design space for the Monoid abstraction in Swift

Monoid.swift

/*
 This gist contains an analysis of the design space for abstractions in a type system like Swift's.
 It focuses on Monoid as an example but the same set of tradeoffs apply to any abstraction.
 As such, it focuses on a single abstraction and does not explore issues that arise when designing
 an abstraction hierarchy in depth.

 The matrix below describes some of the design important design tradeoffs for various approaches including:
 - OO style protocols such as `Monoid { var identity: Self ... }
    (Haskell also adopts this approach for many abstractions, including for Monoid)
 - ML signature style static protocols with empty enum conformances analagous with ML structures
 - type-erased witness style
 - "middle way" as in the Monoid protocol above

                                    OO              ML              "middle way"            witness
 compositionality                   some            yes             yes                     yes
 multiple conformances              with wrappers   yes             yes                     yes
 supports equality                  n/a             yes             yes                     no
 type-level support                 no              yes             with Static refinement  no
 dynamic parameterization           no              no              yes                     yes
 dictionary passing                 implict         explicit        explicit*               explicit
 usage-site syntactic sugar         n/a             with helper     with helper             direct
 optimizable                        yes             yes             yes                     type-erasure hinders optimizer
 abstraction refinement             yes             yes             yes                     with explicit conversions
 algorithms work with conformances  no              no              yes                     yes
    defined in other styles
 convenient ad-hoc instances        no              no              when using              yes
    (i.e. no type decl or extenion)                                 type erasure

 The code below demonstrates how the "middle way" is a strong point in the design space
 which is also able to support ML style and witness (i.e. type-erased) styles.
 This approach models the abstraction explicitly in a way that is able to capture most
 of the benefits and avoid most of the drawbacks of the other styles, especially when
 a "full featured" approach adopting

 Different use cases are important for different abstractions so it is good to be aware of your
 options and the tradeoffs involved when deciding on a design for a specific abstraction
 or family of abstractions.

    *The "middle way" style can support implicit dictionary passing when using constraints such as
    `where Element: Monoid, Element.Value == Element`
 */

/// A "middle ground" design for abstractions that shares with ML-style
/// explicit modeling of the abstraction independent of the subject types
/// but moved to the instance level, allowing algorithms to be written
/// in terms of this protocol while still supporting type erasure
protocol Monoid {
    associatedtype Value

    /// must obey identity laws with respect to `combine`
    /* let */ var identity: Value { get }

    /// must be associative and referrentially transparent
    func combine(_ lhs: inout Value, _ rhs: Value)
}
extension Monoid {
    func combine(_ lhs: Value, _ rhs: Value) -> Value {
        var lhs = lhs
        combine(&lhs, rhs)
        return lhs
    }
}

// MARK: - ML-style

/// If desired, type-level monoids can still be supported and integrate
/// seamlessly with the rest of the design.
///
/// This approach to abstraction can also be useful in demonstrating the
/// conformance is not dynamically parameterizable via initializers, properties, captures, etc
///
/// - note: Conformces must be empty structs instead of empty enums
///         in order to be used at the instance level.
///         It is important that these structs be empty to preserve the static semantic requirement.
protocol StaticMonoid: Monoid {
    // redeclared to support inference of `Value` in conforming types
    associatedtype Value

    /// must obey identity laws with respect to `combine`
    static var identity: Value { get }

    /// must be associative
    static func combine(_ lhs: inout Value, _ rhs: Value)
}
extension StaticMonoid {
    /// Instance level members should not be implemented by conforming types
    /* final */ var identity: Value { return Self.identity }
    /* final */ func combine(_ lhs: inout Value, _ rhs: Value) {
        Self.combine(&lhs, rhs)
    }
    static func combine(_ lhs: Value, _ rhs: Value) -> Value {
        var lhs = lhs
        combine(&lhs, rhs)
        return lhs
    }
}

// MARK: - Witness / type-erased

/// This would still be useful even with generalized existentials if
/// supporting ad-hoc witness-function style is desired
struct AnyMonoid<Value>: Monoid {
    let identity: Value
    private let _combine: (inout Value, Value) -> Void

    init(identity: Value, combine: @escaping (inout Value, Value) -> Void) {
        self.identity = identity
        _combine = combine
    }

    init<M: Monoid>(_ m: M) where M.Value == Value {
        identity = m.identity
        _combine = m.combine
    }

    // if we want to support ML module-style case-less enums
    init<M: StaticMonoid>(_ m: M.Type) where M.Value == Value {
        identity = m.identity
        _combine = m.combine
    }

    func combine(_ lhs: inout Value, _ rhs: Value) {
        return _combine(&lhs, rhs)
    }
}

/// This shouldn't be necessary with generalized existentials
/// which would allow us to say `Monoid where Self: Equatable, Value == Foo`
/// In the meantime, this allows us to store compare monoids when necessary
///
/// It could also be interesting to support `AnyHashableMonoid` which would
/// allow us to put them into a `Set` or `Dictionary`. For example, it could be useful to
/// have a dictionary with monoid keys and currently accumulated values.
/// This might allow a data processing operation that performs multiple combining operations
/// to unique the monoids it is using and ensure redundant computation is not performed.
struct AnyEquatableMonoid<Value: Equatable>: Monoid {
    let identity: Value
    private let _combine: (inout Value, Value) -> Void
    private let monoid: Any
    private let equals: (Any) -> Bool

    init<M: Monoid>(_ monoid: M) where M.Value == Value, M: Equatable {
        identity = monoid.identity
        _combine = monoid.combine
        self.monoid = monoid
        equals = { other in
            guard let other = other as? M else {
                return false
            }
            return other == monoid
        }
    }

    func combine(_ lhs: inout Value, _ rhs: Value) {
        return _combine(&lhs, rhs)
    }
}
extension AnyEquatableMonoid: Equatable {
    static func == (_ lhs: AnyEquatableMonoid<Value>, _ rhs: AnyEquatableMonoid<Value>) -> Bool {
        return lhs.identity == rhs.identity && lhs.equals(rhs.monoid)
    }
}

// MARK - tuple2

struct MonoidTuple2<First, Second>: Monoid where First: Monoid, Second: Monoid {
    let first: First
    let second: Second

    // not sure why the compiler fails to infer this
    typealias Value = (First.Value, Second.Value)

    var identity: (First.Value, Second.Value) {
        return (first.identity, second.identity)
    }
    func combine(_ lhs: inout (First.Value, Second.Value), _ rhs: (First.Value, Second.Value)) {
        first.combine(&lhs.0, rhs.0)
        second.combine(&lhs.1, rhs.1)
    }
}
func tuple2M<First, Second>(_ first: MonoidSugar<First>, _ second: MonoidSugar<Second>) -> MonoidTuple2<First, Second> {
    return MonoidTuple2(first: first.monoid, second: second.monoid)
}

// we can also use a custom tuple type as below that can conform to protocols (such as `Equatable`) directly
// however, we lose some features of Swift tuples such as implicit conversion of multi-argument functions
struct Tuple2<First, Second> {
    var first: First
    var second: Second
}
extension Tuple2: Equatable where First: Equatable, Second: Equatable {}
extension Tuple2: Hashable where First: Hashable, Second: Hashable {}
func tuple2<First, Second>(_ first: First, _ second: Second) -> Tuple2<First, Second> {
    return Tuple2(first: first, second: second)
}
func tuple2M<First, Second>(_ first: MonoidSugar<First>, _ second: MonoidSugar<Second>) -> Tuple2<First, Second> {
    return Tuple2(first: first.monoid, second: second.monoid)
}
extension Tuple2: Monoid where First: Monoid, Second: Monoid {
    // not sure why the compiler fails to infer this
    typealias Value = Tuple2<First.Value, Second.Value>

    var identity: Tuple2<First.Value, Second.Value> {
        return tuple2(first.identity, second.identity)
    }
    func combine(_ lhs: inout Tuple2<First.Value, Second.Value>, _ rhs: Tuple2<First.Value, Second.Value>) {
        first.combine(&lhs.first, rhs.first)
        second.combine(&lhs.second, rhs.second)
    }
}

// MARK: - imap

struct MonoidImap<M: Monoid, Value> {
    private let monoid: M
    private let toValue: (M.Value) -> Value
    private let fromValue: (Value) -> M.Value

    // could use the same sugar here
    fileprivate init(_ monoid: M, toValue: @escaping (M.Value) -> Value, fromValue: @escaping (Value) -> M.Value) {
        self.monoid = monoid
        self.fromValue = fromValue
        self.toValue = toValue
    }
}
extension MonoidImap: Monoid {
    var identity: Value {
        return toValue(monoid.identity)
    }
    func combine(_ lhs: inout Value, _ rhs: Value) {
        lhs = toValue(monoid.combine(fromValue(lhs), fromValue(rhs)))
    }
}
extension Monoid {
    // the result could be type-erased but this is exactly the kind of operator
    // opaque return types are intended for and it is trivial to type-erase
    // the result if callers desire that
    func imap<NewValue>(
        toNewValue: @escaping (Value) -> NewValue,
        fromNewValue: @escaping (NewValue) -> Value
    ) -> /* opaque M: Monoid where M.Value == NewValue */ MonoidImap<Self, NewValue> {
        return MonoidImap(self, toValue: toNewValue, fromValue: fromNewValue)
    }
}

// MARK: - average

public struct Average<A: BinaryFloatingPoint>: Equatable, Hashable {
    fileprivate let count: Int
    fileprivate let sum: A

    public var average: A? {
        return self.count == 0 ? nil : .some(sum / A(count))
    }

    public init(count: Int, sum: A) {
        self.count = count
        self.sum = sum
    }
}

extension MonoidSugar where M.Value: BinaryFloatingPoint {
    // the return type looks nasty, but fortunately when opaque return types come we will not have to write it out explicitly!
    // we could also use an erased return type but that is not a good idea - this is exactly the kind of operator return types are meant for
    // callers can trivially erase the type if desired
    func average() -> /* opaque R: Monoid where R.Value == Average<M.Value> */ MonoidImap<MonoidTuple2<Sum<Int>, Sum<M.Value>>, Average<M.Value>> {
        return tuple2M(.sum(), .sum()).imap(
            toNewValue: Average.init,
            fromNewValue: { ($0.count, $0.sum) }
        )
    }
}

// MARK: - endo

struct Endo<Domain>/*: Monoid*/ {
    typealias Value = (inout Domain) -> Void
    let identity: Value = { _ in }
    // this should work but doesn't due to a compiler bug: https://twitter.com/jckarter/status/1082421111982219264
    // we could implement this if our combine signature used a return value instead of inout
    /*func combine(_ lhs: inout @escaping Value, _ rhs: @escaping Value) {
        lhs = { [lhs] domainValue in
            lhs(&domainValue)
            rhs(&domainValue)
        }
    }*/

    // the return value combine implementation (though it doesn't meet the requirement
    // of the Monoid protocol in this file)
    func combine(_ lhs: @escaping Value, _ rhs: @escaping Value) -> Value {
        return { domainValue in
            lhs(&domainValue)
            rhs(&domainValue)
        }
    }
}
extension/* <Domain> */ MonoidSugar /* where M == Endo<Domain> */ {
    // this would work if the
    /*static func endo<Domain>() -> MonoidSugar<Endo<Domain>> {
        return .init(monoid: Endo())
    }*/
}

// MARK: - pointwise

struct Pointwise<Domain, M: Monoid>/*: Monoid*/ {
    typealias Value = (Domain) -> M.Value

    let monoid: M

    var identity: Value {
        return { _ in self.monoid.identity }
    }

    // this should work but doesn't due to a compiler bug: https://twitter.com/jckarter/status/1082421111982219264
    // we could implement this if our combine signature used a return value instead of inout
    /*func combine(_ lhs: inout @escaping Value, _ rhs: @escaping Value) {
        lhs = { [lhs] in self.monoid.combine(lhs($0), rhs($0)) }
    }*/

    // the return value combine implementation (though it doesn't meet the requirement
    // of the Monoid protocol in this file)
    func combine(_ lhs: @escaping Value, _ rhs: @escaping Value) -> Value {
        return { self.monoid.combine(lhs($0), rhs($0)) }
    }
}
extension /* <Domain, Into: Monoid> */ MonoidSugar /* where M == Pointwise<Domain, Into> */ {
    /*static func pointwise<Domain, M: Monoid>(into monoid: M) -> MonoidSugar<Pointwise<Domain, M>> {
        return .init(monoid: Pointwise(monoid: monoid))
    }*/
}

// MARK: - joined (i.e. RangeReplaceableCollection)

struct Joined<C: RangeReplaceableCollection>: Monoid {
    let identity = C()
    let separator: C.Element
    func combine(_ lhs: inout C, _ rhs: C) {
        if !lhs.isEmpty {
            // copied from https://github.com/pointfreeco/swift-algebras/blob/monoid/Sources/Monoid/Instances/RangeReplaceableCollection.swift
            // but is this correct?  should separator get appended if rhs is empty???
            lhs.append(separator)
        }
        lhs.append(contentsOf: rhs)
    }
}

extension MonoidSugar {
    static func joined<C: RangeReplaceableCollection>(separator: C.Element) -> MonoidSugar<Joined<C>> {
        return .init(monoid: Joined(separator: separator))
    }
}

// MARK: - Usage

struct MonoidSugar<M: Monoid> {
    let monoid: M
}
extension Sequence {
    func fold<M: Monoid>(_ monoid: M) -> M.Value where M.Value == Element {
        return reduce(monoid.identity, monoid.combine)
    }
    func foldWithSugar<M: Monoid>(_ wrapper: MonoidSugar<M>) -> M.Value where M.Value == Element {
        return reduce(wrapper.monoid.identity, wrapper.monoid.combine)
    }
}

struct Sum<N: Numeric>: Monoid {
    let identity: N = 0
    func combine(_ lhs: inout N, _ rhs: N) {
        lhs += rhs
    }
}
extension/* <N: Numeric> */ MonoidSugar /*where M == Sum<N>*/ {
    static func sum<N: Numeric>() -> MonoidSugar<Sum<N>> { return .init(monoid: Sum()) }
}

struct StaticSum<N: Numeric>: StaticMonoid {
    static var identity: N { return 0 }
    static func combine(_ lhs: inout N, _ rhs: N) {
        lhs += rhs
    }
}
extension/* <N: Numeric> */ MonoidSugar /*where M == StaticSum<N>*/ {
    static var staticSum: MonoidSugar<StaticSum<Double>> { return .init(monoid: StaticSum()) }
}

// maybe we'll get generic properties someday...  we could use generic factory methods like sum() instead...
let AnySum = AnyMonoid(identity: 0 as Double, combine: +=)
extension MonoidSugar where M == AnyMonoid<Double> {
    static var anySum: MonoidSugar<AnyMonoid<Double>> { return .init(monoid: AnyMonoid<Double>(AnySum)) }
}


func examples() {
    let sequence = [1.0, 2.0, 3.0, 4.0]
    _ = sequence.fold(Sum())
    _ = sequence.foldWithSugar(.sum())
    _ = sequence.fold(StaticSum())
    _ = sequence.foldWithSugar(.staticSum)
    _ = sequence.fold(AnySum)
    _ = sequence.foldWithSugar(.anySum)
}