First Scala macro...

MacroTest.scala

import language.experimental.macros
import scala.reflect.makro.Context

object MacroTest {
  
  def lookup_builder(t: List[(Int, Int)], d: Int): Int => Int = macro lookup_builder_impl
  
  def lookup_builder_impl(c: Context)(t: c.Expr[List[(Int, Int)]], d: c.Expr[Int]): c.Expr[Int => Int] = {
    import c.mirror._
    import c.universe._
        
    c.reify(x => t.splice.filter(_._1 <= x).lastOption.map(_._2).getOrElse(d.splice))
  }
  
}

RunMe.scala

object Helper {
  def time(f: => Any): String = {
    val t = System.currentTimeMillis
    f
    "Your function took: " + (System.currentTimeMillis - t) + " to run."
  }
}

object RunMe extends App {
  import MacroTest._
  import Helper._
  val a = 0 to 1000000
  val x = lookup_builder(List((1, 1), (2, 3), (3, 4), (4, 3), (6, 2), (8, 3), (9, 3), (10, 2), (11, 1), (12, 0)), 0)
  println(List(1, 7, 6, 20, -10) map x)
  println(time(a map x))
}

UglyButDamnFastReflection.scala

import scala.tools.reflect.Eval
import scala.reflect.base.{TreeCreator, TypeCreator}
import scala.reflect.base.{Universe => BaseUniverse}  
import scala.reflect.base.MirrorOf
import scala.reflect.api.Universe

case class MyTC(a: Any) extends TreeCreator {
   def apply[U <: BaseUniverse with Singleton](m: MirrorOf[U]): U # Tree = {
     import m.universe._
     a.asInstanceOf[U # Tree]
   } 
}

object Helper {
  
  
  def time(f: => Any): String = {
    val t = System.currentTimeMillis
    f
    "Your function took: " + (System.currentTimeMillis - t) + " to run."
  }
  
  def runtime_lookup_builder(t: List[(Int, Int)], d: Int): Int => Int = {
    import scala.reflect.runtime.universe._
    def expr_mkr(t: List[(Int, Int)], d: Int): Tree = {
      val vmcount = t.size
      vmcount match {
        case 0 => Literal(Constant(d))
        case 1 => {
          val (test: Int, high: Int) = t.head
          If(Apply(Select(Ident(newTermName("x")), newTermName("$less")), List(Literal(Constant(test)))),Literal(Constant(d)), Literal(Constant(high)))           
        }
        case _ => {
          val p = t.size / 2
          val (test, highdefault) =  t(p)
          val before_pivot = t.take(p)
          val after_pivot  = t.drop(p + 1)
          If(Apply(Select(Ident(newTermName("x")), newTermName("$less")), List(Literal(Constant(test)))), expr_mkr(before_pivot, d), expr_mkr(after_pivot, highdefault))            
        }        
      }
    }
    
    val a = Function(List(ValDef(Modifiers(), newTermName("x"), Ident(newTypeName("Int")), EmptyTree)), expr_mkr(t, d))
    println(a)
    Expr[Int => Int](scala.reflect.runtime.currentMirror, MyTC(a)).eval
  }
}

object TestIt {

  def main(args: Array[String]): Unit = {
    import Helper._
    val a = 0 to 1000000
    val lookup_table = List((1, 1), (2, 3), (3, 4), (4, 3), (6, 2), (8, 3), (9, 3), (10, 2), (11, 1), (12, 0))
    def lookup_fn(t: List[(Int, Int)], d: Int): Int => Int = x => t.filter(_._1 <= x).lastOption.map(_._2).getOrElse(d)

    val x = runtime_lookup_builder(lookup_table, 0)
    val y = lookup_fn(lookup_table, 0)
  
    println(List(1, 7, 6, 20, -10) map x)
    println(List(1, 7, 6, 20, -10) map y)
    1 to 10 foreach { i =>
      println(time(a map x))
      println(time(a map y))
      //println(time(a map z))
    }
  }
}