Markov algorithms in Scala

Now here’s the Scala code for Markov algorithms. I mostly followed the form of the Haskell code, except for string processing, which is done with StringBuilders to improve performance. Definitely a premature optimization.

case class StepParams(theta: String, phi: String, b: Int, a: Int)

class Algorithm(params: Array[StepParams]) {
  private def replaceIfPossible(p: StepParams, s: StringBuilder) =
  {
    val i = s.indexOf(p.theta)
    if (i != -1)
    {
      s.replace(i, i + p.theta.length, p.phi)
      true
    }
    else false
  }

  private def execLoop(word: StringBuilder, step: Int): String =
  {
    if (step == params.length)
      word.toString
    else if (replaceIfPossible(params(step), word))
      execLoop(word, params(step).b)
    else
      execLoop(word, params(step).a)
  }

  def exec(in: String) = execLoop(new StringBuilder(in), 0)
}

object Markov {
  val absDiff = new Algorithm(Array(StepParams("ab", "" , 0, 1),
                                    StepParams("a" , "c", 1, 2),
                                    StepParams("b" , "c", 2, 3)))

  val min = new Algorithm(Array(StepParams("ab", "d" , 1, 3),
                                StepParams("ad", "d" , 2, 3),
                                StepParams("db", "dd", 1, 3),
                                StepParams("a" , ""  , 3, 4),
                                StepParams("b" , ""  , 4, 5)))

  // The gcd algorithm, Exercise 8, Section 1.1
  val gcd = new Algorithm(Array(StepParams("ab", "" , 1, 2),
                                StepParams(""  , "c", 0, 2),
                                StepParams("a" , "b", 2, 3),
                                StepParams("c" , "a", 3, 4),
                                StepParams("b" , "b", 0, 5)))

  def replicate(n: Int, c: Char) =
  {
    val sb = new StringBuffer(n)
    for (i <- 1 to n)
      sb.append(c)
    sb.toString
  }

  def buildGcdString(m: Int, n: Int) = replicate(m, 'a') + replicate(n, 'b')

  def main(args: Array[String])
  {
    val in = if (args.length > 0) args(0) else "aaabb"
    println("absDiff: " + absDiff.exec(in))
    println("min    : " + min.exec(in))
    println("gcd    : " + gcd.exec(in))
  }
}

After loading this in the interpreter we can try it:

scala> Markov.gcd.exec(Markov.buildGcdString(24, 16))
res1: String = aaaaaaaa