monoids.swift

import Foundation

protocol Monoid {
    static var zero: Self { get }
    func appending(_: Self) -> Self
}

struct AnyMonoid<Type> {
    var zero: Type
    let append: (Type, Type) -> Type
}

extension AnyMonoid where Type: Monoid {
    init() {
        zero = Type.zero
        append = Type.reducer
    }
}

extension Monoid {
    mutating func append(_ other: Self) {
        self = self.appending(other)
    }
    static var reducer: (Self, Self) -> Self {
        return { x, y in x.appending(y) }
    }
}

extension Int: Monoid {
    static let zero = 0
    func appending(_ other: Int) -> Int {
        return self + other
    }
}

extension Sequence {
    func reduced(_ monoid: AnyMonoid<Iterator.Element>) -> Iterator.Element {
        return reduce(monoid.zero, monoid.append)
    }
}

extension Sequence where Iterator.Element: Monoid {
    func reduced() -> Iterator.Element {
        var result = Iterator.Element.zero
        for el in self {
            result = result.appending(el)
        }
        return result
    }
}

extension Array: Monoid {
    static var zero: [Element] { return [] }
    
    func appending(_ other: [Element]) -> [Element] {
        var result = self
        result += other
        return result
    }
}

extension Array {
    func parallelReduced(_ m: AnyMonoid<Element>) -> Element {
        guard count > 2 else { return reduced(m) }
        let halfWay = count / 2
        var results = Array<Element?>(repeating: nil, count: 2)
        
        DispatchQueue.concurrentPerform(iterations: 2) { i in
            let range = i == 0 ? startIndex..<halfWay : halfWay..<endIndex
            results[i] = self[range].reduced(m)
        }
        return results.lazy.map { $0! }.reduced(m)
        
    }
}

extension Array where Element: Monoid {
    func parallelReduced() -> Element {
        return parallelReduced(AnyMonoid())
    }
}

let min = AnyMonoid(zero: Int.max, append: Swift.min)
let max = AnyMonoid(zero: Int.min, append: Swift.max)

Array(1..<100).reduced(max)

[[1,2], [3,4]].reduced()

Array(1..<1000).parallelReduced(max)