Dmitry K fehu

💭

it's compiling...

fehu / cached recursion

Last active September 18, 2019 20:33

cached recursion function for Scala, it's performance comparison with Y combinator for calculating fibonacci numbers

	def cachedRec[A, B](rec: (A => B) => (A => B)): A => CachedRecResult[A, B] = {
	val cache = mutable.HashMap.empty[A, B]
	// fixed-point combinator
	def YY(f: (A => B) => (A => B)): A => B = {
	a => cache.getOrElse(a, {
	val b = rec(YY(rec))(a)
	cache += a -> b
	b
	})
	}