DEV Community

manufacturist
manufacturist

Posted on

1

Favourite piece of Scala code

My favorite piece of Scala code is simple. It's not related to functional programming, typelevel / zio / akka libraries or concurrency.

It simply applies a set of operations on a string, and with the same set of operations, you can reconstruct the original string from the mutated one.

There are three operations: Keep, Insert, and Delete. To represent them as a sequence of operations in JSON, we can assign each operation a type:

  • Keep could be a number, indicating how many characters to keep
  • Insert can be represented by a string
  • Delete can be represented by an array, containing a string element

For example:

mutationLoop([3], "foo")          = "foo"
mutationLoop(["foo"], "bar")      = "foobar"
mutationLoop([["foo"]], "foobar") = "bar"

// Using them all together
mutationLoop(["foo", 2, ["r"], "z"], "bar") = "foobaz"
Enter fullscreen mode Exit fullscreen mode

When we need to store different versions of a string, we can save space by storing the deltas instead of the full strings. This works well for large strings, but it may not be as useful for smaller strings.


What does the implementation look like?

We need to traverse all operations and apply them one by one:

  • For keep, we need to skip a certain number of characters
  • For insert, we need to inject a substring into a string
  • For delete, we need to remove a substring from a string

Using the circe library, the implementation is as follows:

object KeepOperation {
def unapply(op: Json): Option[Int] =
op.asNumber.flatMap(_.toInt)
}
object InsertOperation {
def unapply(op: Json): Option[String] =
op.asString
}
object DeleteOperation {
def unapply(op: Json): Option[String] = {
val isSingletonArray = op.asArray.exists(_.size == 1)
val containsString = op.asArray.exists(_.head.isString)
if (isSingletonArray && containsString) {
op.asArray.flatMap(_.head.asString)
} else None
}
}
@scala.annotation.tailrec
def mutationLoop(
operations: Vector[Json],
builder: StringBuilder,
currentPosition: Int = 0
): Either[Throwable, String] =
if (operations.isEmpty) Right(builder.result())
else operations.head match {
case KeepOperation(toKeep) =>
mutationLoop(operations.tail, builder, currentPosition + toKeep)
case InsertOperation(toInsert) =>
val (left, right) = builder.splitAt(currentPosition)
val updatedBuilder = left ++= toInsert ++= right
val newPosition = currentPosition + toInsert.length
mutationLoop(operations.tail, updatedBuilder, newPosition)
case DeleteOperation(toDelete) =>
val (left, right) = builder.splitAt(currentPosition)
val updatedBuilder = left ++= right.substring(toDelete.length)
mutationLoop(operations.tail, updatedBuilder, currentPosition)
case unknownOperation =>
Left(new IllegalArgumentException(s"Invalid operation $unknownOperation"))
}

NB1. The delete operation does not do anything with the string value itself, besides counting the number of characters that need to be deleted. However, it is used when reverting an operation, to recreate the original string

NB2. If we didn't need to be able to revert, instead of an array with a string, we could have specified a negative integer, telling us how many characters we need to remove

To revert the changes, we simply keep the order of the operations, replacing insert operations with delete operations and vice versa:

def applyOps(
operations: Vector[Json],
target: String,
mustRevert: Boolean = false
): Either[Throwable, String] = {
val ops = if (mustRevert) operations.map {
case DeleteOperation(toDelete) => Json.fromString(toDelete)
case InsertOperation(toInsert) => Json.fromValues(Vector(Json.fromString(toInsert)))
case op => op
} else operations
mutationLoop(ops, new StringBuilder(target))
}

And putting it to good use:

import io.circe.parser.parse
val json = """[["Not t"], "T", 10, ["bad"], "good"]"""
val ops = parse(json).map(_.asArray.get).getOrElse(Vector.empty)
val Right(mutated) = applyOps(ops, "Not testing is bad")
// mutated = "Testing is good"
val Right(original) = applyOps(ops, mutated, mustRevert = true)
// original = "Not testing is bad"

Why is this my favourite code snippet?

It reminds me of simpler times and humble beginnings, when we didn't take basic building blocks for granted and were mindful of every line of code written, constantly trying to give our best with the little experience we had.

Chef Slowik in the movie The Menu experiences something similar at the end of it, when cooking a cheeseburger. He is reminded of the simple things that ignited his passion for cooking.

Similarly, this snippet of code reminds me of why I enjoy programming.

AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

Top comments (0)

Billboard image

Create up to 10 Postgres Databases on Neon's free plan.

If you're starting a new project, Neon has got your databases covered. No credit cards. No trials. No getting in your way.

Try Neon for Free →

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay