memoize.swift

// Naive memoize function
/// MARK - Memoize
func memo_rec<In: Hashable, Out>(yf f: ((In) -> Out) -> ((In) -> Out)) -> ((In) -> Out) {
  var hash = [In: Out]()
  func aux(_ x: In) -> Out {
    if let hf  = hash[x] {
      return hf
    } else {
      let y = f(aux)(x) // (f aux: (In) -> Out):(In) -> Out
      hash[x] = y
      return y
    }
  }
  return aux
}


/// Sample Usage 

public let fib = memo_rec { (f: ((Int) -> Double)) -> ((Int) -> Double) in
  return { (i:Int) in
    if i < 2 {
      return Double(i)
    } else {
      return (f(i - 1) + f(i - 2))
    }
  }
}