Foldable built on a bedrock of Monoids

List_monoid_foldable.swift

/*
If `Monoid` and `Foldable` are predefined, it's possible to create data structures that
receive many default methods, simply by implementing the `Monoid` and `Foldable` protocols.

These data structures could be Trees or Lists, or the built in Array.

Here's an example with a basic implementation of a List:
*/

enum List<Element> {
  case Nil
  indirect case Cons(Element, List<Element>)
  
  // Used to make `List` a `Monoid`
  func append(ys: List) -> List {
    switch self {
    case .Nil: return ys
    case let .Cons(head, tail): return
      .Cons(head, tail.append(ys))
    }
  }
}


/* Make List a `Monoid` */
extension List: Monoid {
  static func mempty() -> List {
    return .Nil
  }
  
  static func mappend(a: List, _ b: List) -> List {
    return a.append(b)
  }
}


/* Make List `Foldable` */
extension List: Foldable {
  func foldMap<M: Monoid>(f: Element -> M) -> M {
    switch self {
    case .Nil: return .mempty()
    case let .Cons(head, tail): return
      .mappend(f(head), tail.foldMap(f))
    }
  }
}


/* build some lists */
let listA = List.Cons(1,.Cons(2, .Nil))
let listB = List.Cons(5,.Cons(11,.Cons(3,.Nil)))
let listC = List.mappend(listA, listB) // use Monoid method to append lists


/* As List implements both Monoid and Foldable we get lots of functions for free! */

listC.sum             // 22
listB.product         // 165
listB.contains(4)     // false
listA.isEmpty         // false
List<Int>.Nil.isEmpty // true
listC.count           // 5
listC.maxElement()    // 11
listC.minElement()    // 1
listB.any { $0 > 4 }  // true
listA.all { $0 > 1 }  // false

let listD = List.Cons("Hel",.Cons("lo",.Cons(" world",.Nil)))
listD.fold() // "Hello world"


/* The Monoid and Foldable protocols with various instances are defined below */

many_monoids.swift

// identity function will come in handy
func id<A>(a: A) -> A { return a }

// as will curry
func curry<A,B,C>(f: (A,B) -> C) -> A -> B -> C {
  return { a in { b in f(a,b) } }
}

// Let's just pretend this Num protocol includes all numeric types!
protocol Num: IntegerLiteralConvertible, IntegerArithmeticType {}
extension Int: Num {}

/* ++ Monoid ++ */

protocol Monoid {
  static func mempty() -> Self
  static func mappend(a: Self, _ b: Self) -> Self
  static func mconcat(a: [Self]) -> Self
}

/* All Monoids get a function for free! 🍺 */

extension Monoid {
  static func mconcat(a: [Self]) -> Self {
    return a.reduce(mempty(), combine: mappend)
  }
}


/* ++ Many Monoids ++ */

extension Array: Monoid {
  static func mempty() -> [Element] {
    return []
  }
  
  static func mappend(a: [Element], _ b: [Element]) -> [Element] {
    return a + b
  }
}


extension String: Monoid {
  static func mempty() -> String {
    return ""
  }
  
  static func mappend(a: String, _ b: String) -> String {
    return a + b
  }
}


struct Sum<T: Num> {
  let value: T
  init(_ v: T) { value = v }
}

extension Sum: Monoid {
  static func mempty() -> Sum {
    return Sum(0)
  }
  
  static func mappend(a: Sum, _ b: Sum) -> Sum {
    return Sum(a.value + b.value)
  }
}


struct Product<T: Num> {
  let value: T
  init(_ v: T) { value = v }
}

extension Product: Monoid {
  static func mempty() -> Product {
    return Product(1)
  }
  
  static func mappend(a: Product, _ b: Product) -> Product {
    return Product(a.value * b.value)
  }
}


struct First<T> {
  let value: Optional<T>
  init(_ v: Optional<T>) { value = v }
}

extension First: Monoid {
  static func mempty() -> First {
    return First(.None)
  }
  
  static func mappend(a: First, _ b: First) -> First {
    return a.value.map { _ in a } ?? b
  }
}


struct Last<T> {
  let value: Optional<T>
  init(_ v: Optional<T>) { value = v }
}

extension Last: Monoid {
  static func mempty() -> Last {
    return Last(.None)
  }
  
  static func mappend(a: Last, _ b: Last) -> Last {
    return b.value.map { _ in b } ?? a
  }
}


struct All {
  let value: Bool
  init(_ v: Bool) { value = v }
}

extension All: Monoid {
  static func mempty() -> All {
    return All(true)
  }
  
  static func mappend(a: All, _ b: All) -> All {
    return All(a.value && b.value)
  }
}


struct Any {
  let value: Bool
  init(_ v: Bool) { value = v }
}

extension Any: Monoid {
  static func mempty() -> Any {
    return Any(false)
  }
  
  static func mappend(a: Any, _ b: Any) -> Any {
    return Any(a.value || b.value)
  }
}


struct Min<Element: Comparable> {
  let value: Element?
  init(_ v: Element?) { value = v }
}

extension Min: Monoid {
  static func mempty() -> Min {
    return Min(.None)
  }
  
  static func mappend(a: Min, _ b: Min) -> Min {
    switch (a.value, b.value) {
    case (.Some, .None): return a
    case (.None, .Some): return b
    case let (.Some(x), .Some(y)) where x <= y: return a
    default: return b
    }
  }
}


struct Max<Element: Comparable> {
  let value: Element?
  init(_ v: Element?) { value = v }
}

extension Max: Monoid {
  static func mempty() -> Max {
    return Max(.None)
  }
  
  static func mappend(a: Max, _ b: Max) -> Max {
    switch (a.value, b.value) {
    case (.Some, .None): return a
    case (.None, .Some): return b
    case let (.Some(x), .Some(y)) where x >= y: return a
    default: return b
    }
  }
}


struct Endo<A> {
  let value: A -> A
  init(_ v: A -> A) { value = v }
}

extension Endo: Monoid {
  static func mempty() -> Endo {
    return Endo(id)
  }
  
  static func mappend(f: Endo, _ g: Endo) -> Endo {
    return Endo( { g.value(f.value($0)) } )
  }
}

swift_foldable.swift

/* ++ Foldable ++ */

protocol Foldable {
  typealias Element
  func foldMap<M: Monoid>(f: Element -> M) -> M
}

/* All Foldables get many functions for free 🍻 */

extension Foldable {
  func foldr<B>(initial: B, combine: Element -> B -> B) -> B {
    return foldMap { Endo(combine($0)) }.value(initial)
  }
  
  func foldMap<M: Monoid>(f: Element -> M) -> M {
    let mappend = curry(M.mappend)
    return foldr(M.mempty()) { mappend(f($0)) }
  }
  
  func any(p: Element -> Bool) -> Bool {
    return foldMap { Any(p($0)) }.value
  }
  
  func all(p: Element -> Bool) -> Bool {
    return foldMap { All(p($0)) }.value
  }
  
  var isEmpty: Bool {
    return foldr(true) { _ in { _ in false } }
  }

  var count: Int {
    return foldr(0) { _ in { c in c + 1 } }
  }
}

extension Foldable where Element: Monoid {
  func fold() -> Element {
    return foldMap(id)
  }
}

extension Foldable where Element: Num {
  var sum: Element {
    return foldMap(Sum.init).value
  }
  
  var product: Element {
    return foldMap(Product.init).value
  }
}

extension Foldable where Element: Equatable {
  func contains(x: Element) -> Bool {
    return any { $0 == x }
  }
}

extension Foldable where Element: Comparable {
  func minElement() -> Element? {
    return foldMap { Min.init($0) }.value
  }
  
  func maxElement() -> Element? {
    return foldMap { Max.init($0) }.value
  }
}