Memoization in Swift

memo.swift

import Foundation

func perf<T, U>(f: T -> U) -> T -> (NSTimeInterval, U) {
    return {
        (a: T) -> (NSTimeInterval, U) in
        let start = NSDate()
        
        let result = f(a)
        
        return (NSDate().timeIntervalSinceDate(start), result)
    }
}

func memo<T: Hashable, U>(f: T -> U) -> T -> U {
    var cache = [T:U]()
    
    return {
        (a: T) -> U in
        var result = cache[a]
        
        if result == nil {
            result = f(a)
            cache[a] = result
        }
        
        return result!
    }
}

var fib: Int -> Double
fib = {
    (n: Int) -> Double in
    guard n > 0 else { return 0 }
    guard n > 2 else { return 1 }
    return fib(n-1) + fib(n-2)
}

let perfFib = perf(fib)

perfFib(20)

fib = memo(fib)

perfFib(20)
perfFib(100)