beam.scala

def beam[T](
  data:List[List[T]], 
  perplexityFn: List[T] => Double,
  startNode:T,
  beamSize:Int = 10)
:List[(List[T], Double)] = {

  var candidates = List((List(startNode), 0d))

  data.foreach{ case datum:List[T] =>
    candidates = datum.map{ case d:T =>
      candidates.map{ case (c:List[T], p:Double) =>
        val x = c :+ d
        (x, perplexityFn(x))
      }
    }.toList.flatten
    .sortWith{ case(a:(List[T], Double), b:(List[T], Double)) =>
      a._2 > b._2
    }.take(beamSize)

  }

  candidates
}

def beamTest:Unit = {
  val testData = List(
    List("some", "random", "algorithm","q","w","e","r","t","y","u","i","o","p","a","s","d","f","g","h","j","k","l","z","x","c","v","b","n","m"),
    List("that", "prefers", "to", "have","q","w","e","r","t","y","u","i","o","p","a","s","d","f","g","h","j","k","l","z","x","c","v","b","n","m"),
    List("more", "longer","q","w","e","r","t","y","u","i","o","p","a","s","d","f","g","h","j","k","l","z","x","c","v","b","n","m"),
    List("words","q","w","e","r","t","y","u","i","o","p","a","s","d","f","g","h","j","k","l","z","x","c","v","b","n","m")
  )

  val res = beam[String](testData, (x:List[String]) => x.mkString(" ").length.toDouble, "", 5)
  res.map{ r => println(r._1.mkString(" ") +"\t\t->\t"+r._2) }
}

scala> beamTest
 algorithm prefers longer words         ->      31.0
 algorithm prefers more words           ->      29.0
 algorithm that longer words            ->      28.0
 random prefers longer words            ->      28.0
 algorithm have longer words            ->      28.0