port purescript-memoize to scala

readme.md

• https://github.com/paf31/purescript-memoize/blob/v2.0.0/src/Data/Function/Memoize.purs
• https://github.com/purescript/purescript-lazy/tree/v1.0.0/src/Data

build.sbt

scalaVersion := "2.11.8"

name := "memo"

libraryDependencies += "org.scalaz" %% "scalaz-core" % "7.2.4"

licenses := Seq("MIT License" -> url("http://opensource.org/licenses/mit"))

scalacOptions ++= (
  "-deprecation" ::
  "-unchecked" ::
  "-Xlint" ::
  "-language:existentials" ::
  "-language:higherKinds" ::
  "-language:implicitConversions" ::
  "-Yno-adapted-args" ::
  Nil
)

val unusedWarnings = (
  "-Ywarn-unused" ::
  "-Ywarn-unused-import" ::
  Nil
)

scalacOptions ++= PartialFunction.condOpt(CrossVersion.partialVersion(scalaVersion.value)){
  case Some((2, v)) if v >= 11 => unusedWarnings
}.toList.flatten

Seq(Compile, Test).flatMap(c =>
  scalacOptions in (c, console) ~= {_.filterNot(unusedWarnings.toSet)}
)

Main.scala

package scalaz

object Main {
  def main (args: Array[String]): Unit = {
    val n = 35
    time(fibonacci0(n))
    time(fibonacci2(n))
    time(fibonacci3(n))
  }

  def fibonacci0(n: Int): Int = n match {
    case 0 => 0
    case 1 => 1
    case _ =>
      fibonacci0(n - 1) + fibonacci0(n - 2)
  }

  def fibonacci1(n: Int): Int = n match {
    case 0 => 0
    case 1 => 1
    case _ =>
      fibonacci2(n - 1) + fibonacci2(n - 2)
  }

  val fibonacci2: Int => Int = Tabulate.memoize{
    fibonacci1
  }

  def fibonacci3(x: Int): Int = {
    @annotation.tailrec
    def go(n: Int, m: Int, i: Int): Int =
      if(i == 0) {
        n
      } else {
        go(m, n + m, i - 1)
      }
    go(0, 1, x)
  }

  def time[A](f: => A): Unit = {
    val start = System.currentTimeMillis
    val r = f
    println(r + " " + (System.currentTimeMillis - start))
  }
}

NatTrie.scala

package scalaz

final case class NatTrie[A](
  a: Need[A],
  left: Need[NatTrie[A]],
  right: Need[NatTrie[A]]
)

Tabulate.scala

package scalaz

/**
  * @see [[https://github.com/paf31/purescript-memoize/blob/v2.0.0/src/Data/Function/Memoize.purs]]
  */
trait Tabulate[A] {
  def tabulate[R](f: A => R): A => Need[R]
}

object Tabulate {
  def apply[A](implicit A: Tabulate[A]): Tabulate[A] = A

  def memoize[A, B](f: A => B)(implicit A: Tabulate[A]): A => B =
    a => A.tabulate(f)(a).value

  implicit val int: Tabulate[Int] =
    new Tabulate[Int] {
      def tabulate[R](f: Int => R) = { a: Int =>
        def build(n: Int): NatTrie[R] =
          NatTrie(
            Need(f(n)),
            Need(build(n * 2)),
            Need(build((n * 2) + 1))
          )

        def bits(x: Int): List[Boolean] = {
          @annotation.tailrec
          def loop(acc: List[Boolean], n: Int): List[Boolean] = n match {
            case 1 =>
              acc
            case _ =>
              loop((n % 2 != 0) :: acc, n / 2)
          }
          loop(Nil, x)
        }

        def walk[A](xs: List[Boolean], n: NatTrie[A]): Need[A] = {
          xs match {
            case Nil =>
              n.a
            case false :: bs =>
              Bind[Need].bind(n.left)(walk(bs, _))
            case true :: bs =>
              Bind[Need].bind(n.right)(walk(bs, _))
          }
        }

        a match {
          case 0 => Need(f(0))
          case _ =>
            walk(
              bits(if(a > 0) a else -a),
              if (a > 0) build(1) else build(-1)
            )
        }
      }
    }

}