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)

Program.scala

object Program {
  def main(args: Array[String]): Unit = {
    var fib: BigInt => BigInt = null
    
    fib = n =>  {
      n match {
        case x if x <= 2 => 1
        case x => fib(x - 1) + fib(x - 2)      
      } 
    } 

    var perfFib = perf(fib)

    println(perfFib(20))

    fib = memo(fib)

    println(perfFib(20))
    println(perfFib(100))      
  }
  
  def perf[T, U](f: T => U): T => (Long, U) = t => {
    val s = System.nanoTime
    val res = f(t)
    val elapsed = System.nanoTime - s 
    (elapsed, res)
  }
  
  def memo[T, U](f: T => U): T => U = {
    val cache = scala.collection.mutable.Map.empty[T, U]    
    t => {
      if(cache.contains(t)) {
        cache(t)        
      } else {
        val result = f(t)
        cache += t -> result
        result               
      }      
    }
  }  
}