Skip to content

Instantly share code, notes, and snippets.

@erica erica/monoid.swift
Last active Aug 6, 2019

Embed
What would you like to do?
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
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.