Demo using Cats/Dogs to implement lazy memoization, similar to this Haskell gist: https://gist.github.com/beala/d871ae8397167e7035f218a25ddf87dd

beala.scala

package beala

import dogs._

object Beala {

  // ironically dogs doesn't support unsafe operations by default,
  // so we have to build them ourselves (since we know our stream
  // is infinite and will always have elements).
  def head[A](as: Streaming[A]): A =
    as.uncons.getOrElse(sys.error("empty head"))._1

  def get[A](as: Streaming[A], i: Int): A =
    head(as.drop(i))

  lazy val fibs: Streaming[Long] =
    Streaming.from(0).map {
      case 0 => 0L
      case 1 => 1L
      case n => get(fibs, n - 1) + get(fibs, n - 2)
    }.memoize

  def slow(i: Int): Long =
    if (i == 0) 0L
    else if (i == 1) 1L
    else slow(i - 1) + slow(i - 2)

  def fast(i: Int): Long =
    get(fibs, i)
}