infix operator <>: AdditionPrecedence

public protocol Monoid {
    static var empty: Self { get }
    static func <>(lhs: Self, rhs: Self) -> Self
}

public extension Sequence where Element: Monoid {
    func concat() -> Element {
        return reduce(Element.empty, <>)
    }
}

extension Array: Monoid {
    public static var empty: [Element] { return [] }
    public static func <>(lhs: [Element], rhs: [Element]) -> [Element] {
		return lhs.appending(rhs)		
    }
}

extension Dictionary: Monoid {
    public static var empty: [Key: Value] { return [:] }
    public static func <>(lhs: [Key: Value], rhs: [Key: Value]) -> [Key: Value] {
        return lhs.merging(rhs, uniquingKeysWith: { _, newKey in newKey })
    }
}

extension Set: Monoid {
    public static var empty: Set<Element> { return [] }
    public static func <>(lhs: Set<Element>, rhs: Set<Element>) -> Set<Element> {
        return lhs.union(rhs)
    }
}

extension Optional: Monoid where Wrapped: Monoid {
    public static var empty: Wrapped? { return nil }
    public static func <>(lhs: Wrapped?, rhs: Wrapped?) -> Wrapped? {
        guard let lhs = lhs else { return rhs }
        guard let rhs = rhs else { return lhs }
        return lhs <> rhs
    }
}