Reimplementation of `memoize` function from "Advanced Swift", using the least fixed point.

fix+memoize.swift

/// :param: f  A function which takes a function, and returns a function with same signature.
///            The returned function can be made recursive by calling the given function.
///
/// :returns:  A recursive function. The least fixed point of the function returned by `f`.
public func fix<T, R>(f: ((T)->R) -> ((T)->R)) -> (T)->R {
  return { f(fix(f))($0) }
}


// Reimplementation of `memoize` from [Advanced Swift], using `fix`
// let fib  = memoize { f in { x in (x <= 1) ? 1 : f(x - 1) + f(x - 2) } }
public func memoize<A : Hashable, R>(f: (A->R)->(A->R)) -> (A)->R {
  var memo: [A: R] = [:]
  return fix { g in
    { a in
      if let r = memo[a] { return r }
      let r = f(g)(a)
      memo[a] = r
      return r
    }
  }
}

// Original
// let fib = memoize {(fib:(Int)->Int, x:Int) in (x <= 1) ? 1 : fib(x - 1) + fib(x - 2)}
//
// Now
// let fib = memoize { f in { x in (x <= 1) ? 1 : f(x - 1) + f(x - 2) } }
//
// let 𝜑 = Double(fib(45)) / Double(fib(44)) // ≅ 1.61803398874989...


// `memoize` function from [Advanced Swift].
//
// let fib = memoize {(fib:(Int)->Int, x:Int) in (x <= 1) ? 1 : fib(x - 1) + fib(x - 2)}
// let 𝜑 = Double(fib(45)) / Double(fib(44)) // ≅ 1.61803398874989...
//
// func memoize<A : Hashable, R>(body: ((A)->R, A)->R) -> (A)->R {
//   var memo:[A: R] = [:]
//   var memoized: ((A)->R)!
//   memoized = {(a) in
//     if let r = memo[a] { return r }
//     let r = body(memoized, a)
//     memo[a] = r
//     return r
//   }
//   return memoized
// }
//
// [Advanced Swift]: https://developer.apple.com/videos/wwdc/2014/?id=404


//
public func memoize<A : Hashable, B : Hashable, R>
  (f: ((A, B)->R)->((A, B)->R)) -> (A, B)->R
{
  var memo: [A: [B: R]] = [:]
  return fix { g in
    { (a, b) in
      if let r = memo[a]?[b] { return r }
      
      if memo[a] == nil { memo[a] = [:] }
      let r = f(g)(a, b)
      memo[a]![b] = r
      return r     
    }
  }
}

public func memoize<A : Hashable, B : Hashable, C : Hashable, R>
  (f: ((A, B, C)->R)-> ((A, B, C)->R))
  -> (A, B, C)->R
{
  var memo: [A: [B: [C: R]]] = [:]
  return fix { g in
    { (a, b, c) in
      if let r = memo[a]?[b]?[c] { return r }
      
      if memo[a] == nil { memo[a] = [:] }
      if memo[a]![b] == nil { memo[a]![b] = [:] }
      let r = f(g)(a, b, c)
      memo[a]![b]![c] = r
      return r
    }
  }
}