monoid.swift

import Foundation

// 3456789012345678901234567890123456789012345678901234567890123456789012345678

/*
 
 Monoid reduction, for strictly binary operation combination.
 
 Note: The monoid approach does not throw right now.
 
 */

/// An algebraic operation that combines two values to produce another value
/// within the same domain.
public typealias BinaryOperation<Domain> = (_ left: Domain, _ right: Domain) -> Domain

/// An algebraic structure storing a non-associative binary operation and
/// an identity element. Associativity is handled by whatever `reduce` or
/// `fold` operation applies the monoid over a sequence.
public struct Monoid<Domain> {
  /// A calculation that combines two values of `Domain` to produce a value
  /// in `Domain`
  public let operation: BinaryOperation<Domain>

  /// An element of `Domain` that leaves elements of `Domain` unchanged when
  /// combined with them via the operation
  public let identity: Domain
}

public extension SignedNumeric {
  /// The summation monoid for numbers
  static var sum: Monoid<Self> {
    return Monoid<Self>(operation: +, identity: 0)
  }
  
  /// The product monoid for numbers
  static var product: Monoid<Self> {
    return Monoid<Self>(operation: *, identity: 1)
  }
}

public extension Bool {
  /// The `and` monoid for Boolean values
  static var and: Monoid<Bool> {
    return Monoid<Bool>(operation: { $0 && $1 }, identity: true)
  }

  /// The `or` monoid for Boolean values
  static var or: Monoid<Bool> {
    return Monoid<Bool>(operation: { $0 || $1 }, identity: false)
  }
  
  /// The `xor` monoid for Boolean values
  static var xor: Monoid<Bool> {
    return Monoid<Bool>(operation: { $0 != $1 }, identity: false)
  }
}

public extension CGRect {
  /// The union (combination) monoid for CGRect
  static var union: Monoid<CGRect> {
    return Monoid<CGRect>(operation: { $0.union($1) }, identity: .null)
  }
}

public extension SetAlgebra {
  /// The union monoid for set algebra
  static var union: Monoid<Self> {
    return Monoid<Self>(operation: { $0.union($1) }, identity: [])
  }
  
  /// The intersection monoid for set algebra
  ///
  /// - Caution: This returns an empty set instead of the superset of all
  ///   members of `Element`
  static var intersection: Monoid<Self> {
    return Monoid<Self>(operation: { $0.intersection($1) }, identity: [])
  }
}

public extension RangeReplaceableCollection {
  /// The join monoid for range replaceable collections
  static var join: Monoid<Self> {
    return Monoid<Self>(operation: { $0 + $1 }, identity: Self.init())
  }
}

extension Sequence {
  /// Combines the elements of the sequence using a monoid, returning the
  /// result (or the monoid identity, for a no-element sequence).
  ///
  /// - Parameters:
  ///   - monoid: A monoid that stores a binary operation mapping two
  ///     elements of the domain into the domain and an identity, which
  ///     is returned for empty sequences. The result of combining the
  ///     identity with any member of the domain is to return the unchanged
  ///     domain member.
  /// - Returns: The final accumulated value or the monoid identity for
  ///   no-member sequences
  ///
  /// - Complexity: O(*n*), where *n* is the length of the sequence.
  public func reduce(_ monoid: Monoid<Element>) -> Element {
    var iterator = makeIterator()
    guard var accumulator = iterator.next()
      else { return monoid.identity }
    while let element = iterator.next() {
      accumulator = monoid.operation(accumulator, element)
    }
    return accumulator
  }
}

[1, 2, 3, 4].reduce(Int.sum)
let frames = [
  CGRect(x: 10, y: 10, width: 50, height: 50),
  CGRect(x: 40, y: 80, width: 20, height: 30),
  CGRect(x: -5, y: 10, width: 10, height: 10),
]
frames.reduce(CGRect.union)

[true, true, false, true].reduce(Bool.and)
[true, true, false, true].reduce(Bool.or)
[true, true, false, true].reduce(Bool.xor)

["a", "bc"].reduce(String.join)
[[1, 2], [3, 4], [], [5]].reduce([Int].join)
[[Int]]().reduce([Int].join)

extension Sequence {
  /// Combines the elements of a sequence using an
  /// `(Element, Element) -> Element` binary operation that
  /// cannot be represented as a monoid. Non monoid operations
  /// cannot provide an identity, thereby excluding them from
  /// returning a default value.
  ///
  /// The method returns the calculated result or traps on empty
  /// sequences. This trapping approach is congruent to out-of-bounds
  /// indexing for arrays. The caller is responsible for testing
  /// `isEmpty` on the sequence and handling that case.
  ///
  /// * If the sequence has no elements, `reduce` traps
  /// * If the sequence has one element, `reduce` returns that element.
  /// * If the sequence has two or more element, `reduce` returns the
  ///   result of iteratively applying the operator along the partial results
  ///   of the sequence.
  ///
  /// ```
  /// // Traps on empty array
  /// [Int]().reduce { $0 > $1 ? $1 : $0 } // traps
  /// // The result for a single-member array is the only value
  /// [Double(1.2)].reduce { $0 > $1 ? $1 : $0 } // 1.2
  /// // Returns the minimum value
  /// [0.3, -0.3, 2.2, -1.6, -0.2].reduce { $0 > $1 ? $1 : $0 } // -1.6
  /// ```
  ///
  /// `reduce` can, for example, combine elements to calculate minimum bounds
  /// to fit a set of rectangles:
  ///
  ///     let frames = [
  ///       CGRect(x: 10, y: 10, width: 50, height: 50),
  ///       CGRect(x: 40, y: 80, width: 20, height: 30),
  ///       CGRect(x: -5, y: 10, width: 10, height: 10),
  ///     ]
  ///
  ///     frames.reduce({ $0.union($1) })
  ///     // (x: -5.0, y: 10.0, width: 65.0, height: 100.0)
  ///
  /// To handle `(T, U) -> U` binary operations, you must apply
  /// `reduce(:_, :_)`. For example, counting the number of characters
  /// in an array of strings uses an `(Int, String) -> Int` operation
  /// and cannot be calculated using `reduce(:_)`:
  ///
  /// ```
  /// let strings = ["one", "two", "three"]
  /// strings.reduce(0, { $0 + $1.count }) // 11
  /// ```
  ///
  /// Prefer the monoid form of `reduce` wherever an operation
  /// provides an inherent identity. This eliminates the potential for
  /// trapping and the need to test for empty sequences.
  ///
  /// - Parameters:
  ///   - nextPartialResult: A closure that combines an accumulating value and
  ///     an element of the sequence into a new accumulating value, to be used
  ///     in the next call of the `nextPartialResult` closure or returned to
  ///     the caller.
  ///   - partialResult: The accumulated value of the sequence, initialized as the first sequence member
  ///   - current: The next element of the sequence to combine into the partial result
  /// - Returns: The final accumulated value
  /// 
  /// - Complexity: O(*n*), where *n* is the length of the sequence.
  public func reduce(
    _ nextPartialResult:
    (_ partialResult: Element, _ current: Element) throws -> Element
    ) rethrows -> Element {
    var iterator = makeIterator()
    guard var accumulator = iterator.next() else {
      fatalError("Attempted to reduce empty sequence with undefined sequence identity")
    }
    while let element = iterator.next() {
      accumulator = try nextPartialResult(accumulator, element)
    }
    return accumulator
  }
}

let strings = ["one", "two", "three"]
strings.reduce(0, { $0 + $1.count }) // 11

// Uses `Double` due to a weird compiler bug
let minimumValueOne = [Double(1.2)].reduce { $0 > $1 ? $1 : $0 } // 1.2
let minimumValue = [0.3, -0.3, 2.2, -1.6, -0.2].reduce { $0 > $1 ? $1 : $0 } // -1.6
minimumValue