March 2021 - Lensception

Introduction

It isn't every day that you are asked to join Cobb and his team of dream experts to perform a top secret mission. But today is your lucky day. The other members of your team have assembled a dream map of sorts that lays out every possible dream that the target could have. The task you have been assigned is finding the proper dream in which to plant a new idea (perform inception). Your only tools that you'll have available to you are the Scala programming language and the Monocle lens library. Good luck!

The main task in this challenge is to take in a representation of all possible Dreams and plant an Idea into the Dream containing the destinationDreamId. Dreams are recursive data structures that contain zero or more childDreams. Your task is to drill down through all childDreams recursively until you find the one that has an id equal to the provided destinationDreamId. There you will plant the provided idea and return the updated representation of all possible dreams.

final case class Dream(
  id: String,
  idea: Option[Idea],
  childDreams: List[Dream]
)

def inception(
  possibleDreams: Dream,
  destinationDreamId: String,
  idea: Idea
): Dream = ???

Once you are through with that task, there is one more task that will require a more extensive use of the Monocle library to complete:

def updateTotem(
  possibleDreams: Dream,
  authorId: String,
  totem: Totem
): Dream = ???

Getting Started

1. Clone the starter code here. The starter code contains acceptance tests. Get the ChallengeSpec to pass and you are done!
2. Run the tests to ensure you are set up (using sbt test, for example). All tests will be failing for now.

Note that the starter code contains two main elements: the challenge and the fundamentals. The challenge is the problem described above and the fundamentals are simpler, shorter problems you can solve to brush up on your knowledge prior to completing the full challenge. Feel free to skip the fundamentals if you don't feel like you want/need to do them.

Tip: It may be helpful as you are going through to run only the tests for either the fundamentals or the challenge. For example, if you only want to run the fundamental tests, you can do so with sbt 'testOnly **.FundamentalsSpec'.

Fundamentals

Note: You can follow along with the solution code here.

Below are the solutions to all of the fundamental problems for March 2021. These problems are designed to give you everything you need to solve the full challenge for the month.

Monocle High-Level Overview

At a high level, Monocle is an optics library for the Scala programming language. Although the terminology surrounding optics libraries is intimidating, it is actually quite simple once you understand a few basic concepts.

The main purpose of an optics library such as Monocle is to provide tools for working performing purely-functional data manipulations. The two main tools used for doing this are lenses and prisms.

Lenses

Lenses are designed to make it easier to work with product types. If you are not familiar with what a product type is, it is basically just a case class or tuple in Scala. For example:

final case class User(id: String, name: String)

Here User is a product type. The way we can know it is a product type is because a User is the combination of an id and a name. The key word there is and. Product types are any type where the type is made up of sub-fields that have an and relationship to one another. Another way to think of product types is in terms of the intersection between types.

If these terms are too mathematical to make practical sense right now then don't worry. For now just focus on the fact that Lenses are ideal for working with case classes.

Prisms

Just as lenses are designed for working with product types, prisms are designed for working with sum types. In Scala, sum types are usually represented as a sealed hierarchy such as:

sealed trait Animal
case object Dog extends Animal
case object Cat extends Animal

Here we have a type Animal that can be either a Cat or a Dog. Since product types work with fields that are and-ed or intersected together, it is natural that sum types work with fields that are or-ed together. Another way to think of sum types is in terms of the union between types. Here an Animal is the union of Dog and Cat.

Again, if these terms are more confusing than helpful then just forget them for now. For now you don't need to know anything more than that prisms are used for working with sealed hierarchies such as the one above.

Fundamental One

Return the firstName of the primary account holder.

private val primaryFirstName = GenLens[BankAccount](_.holder.primary.name.firstName)

def one(ba: BankAccount): FirstName = {
  primaryFirstName.get(ba)
}

Here we are using a Lens to extract the first name of the primary account holder of a given bank account. The Lens that we are using can be thought of as a recipe for how we can get a FirstName given a BankAccount.

Of course we could solve this problem without lenses. That would look like:

def one(ba: BankAccount): FirstName = {
  ba.holder.primary.name.firstName
}

Of course, this looks easier than using lenses does. But that is because this example is very simple. As we work on other problems you will start to get an intuition for why lenses are useful.

Note that we are using the GenLens macro in order to create our Lens here. This is essentially a way for us to create a Lens with less boilerplate than is normally required. A macro, in general, is a compile-time process that converts a block of code into a different block of code. Here, the compiler will transform our GenLens into an actual Lens so it can be used.

Fundamental Two

Update the firstName of the primary account holder to be "Mal"

def two(ba: BankAccount): BankAccount = {
  primaryFirstName.set(FirstName("Mal"))(ba)
}

This is where lenses start to get really nice. Here we are updating the first name of the primary account holder of a given bank account. Lets look at how we would do this without lenses.

def two(ba: BankAccount): BankAccount = {
  ba.copy(
    holder = ba.holder.copy(
      primary = ba.holder.primary.copy(
        name = ba.holder.primary.name.copy(
          firstName = ba.holder.primary.name.firstName.copy(value = "Mal")
        )
      )
    )
  )
}

Although this isn't a very difficult update, you can see that it becomes quite verbose quickly as we attempt to update nested fields.

Lenses are able to help us make the same update because they are a "recipe" as we discussed earlier. Because they contain the recipe for how to get from a BankAccount to a FirstName, they are able to get and/or set that first name very easily.

Fundamental Three

Update the lastName of the primary and secondary (if exists) account holders to be "Fischer"

private val accountHolder = GenLens[BankAccount](_.holder)
private val primary = GenLens[AccountHolder](_.primary)
private val secondary = GenLens[AccountHolder](_.secondary)
private val lastName = GenLens[Person](_.name.lastName)

def three(ba: BankAccount): BankAccount = {
  val updatedPrimary = accountHolder.composeLens(primary)
    .composeLens(lastName).set(LastName("Fischer"))
  val updatedSecondary = accountHolder.composeLens(secondary)
    .composePrism(some).composeLens(lastName).set(LastName("Fischer"))
  updatedPrimary.compose(updatedSecondary)(ba)
}

With this fundamental we are able to see that lenses and prisms compose with themselves and one another. We are able to start with a lens that gets us from a BankAccount to an AccountHolder. From there, we need lenses to:

• Get from AccountHolder to the primary account holder
• Get from AccountHolder to the secondary account holder
• Finally, we need to be able to go from Person to the last name of that person

From these lenses, we are able to compose them to get from BankAccount to both the primary and secondary account holders' last names.

In addition to this, we have now introduced sum types. Within the composition of the secondary account last name lens you will find a call to composePrism(some). This is a way of telling monocle to update the last name of the secondary account holder if the secondary account holder exists. If the secondary account holder does not exist then nothing will take place. This is a prism because Option is a sum type. Option is a sum type because it can be either a Some or a None.

Fundamental Four

Use a Prism to return the name of the animal if it is a dog, else return None.

private val dogPrism = Prism[Animal, DogName] {
  case Dog(name) => Some(name)
  case _ => None
}(name => Dog(name))

def four(a: Animal): Option[DogName] = {
  dogPrism.getOption(a)
}

Here we have constructed a prism using a constructor where we provide two functions. The first function is telling the Prism how to go from an Animal to an Option[DogName]. The second function is telling the Prism how to go from a DogName to an Animal (in this case a Dog because it is a sub-type of Animal).

Now this prism can be used for conversions from an Animal to a DogName and vice versa.

Fundamental Five

Use a Prism to construct an Animal given a DogName.

def five(d: Animal.DogName): Animal = {
  dogPrism(d)
}

This example is using the same prism as Fundamental Four to convert from an Animal.DogName to an Animal.

Fundamental Six

If the household pet is a dog, append " II" to its name and return the entire household.

private val animalLens = GenLens[Household](_.occupants.pet)

def six(h: Household): Household = {
  animalLens.composePrism(dogPrism)
    .modify(dn => Animal.DogName(dn.value + " II"))(h)
}

Here we are composing the dogPrism we created before with a new animalLens. This tells Monocle how to go from a Household to a DogName. Since it has this mapping, we are now able to call .modify on our composition and use that to update the dogName in place (meaning without modifying the rest of the Household).

Fundamental Seven

Add 1 to every leaf node inside of the tree. Hint: Look at the Plated type-class from Monocle.

private implicit def treePlated[A]: Plated[Tree[A]] = Plated(
  new Traversal[Tree[A],Tree[A]] {
    def modifyF[F[_]: cats.Applicative](f: Tree[A] => F[Tree[A]])(s: Tree[A]): F[Tree[A]] = s match {
      case Tree.Leaf(d) => Tree.Leaf(d).pure[F].widen
      case Tree.Branch(d, l, r) => cats.Applicative[F].product(f(l), f(r)).map(res => Tree.Branch(d, res._1, res._2))
    }
  }
)

def seven(tree: Tree[Int]): Tree[Int] = {
  Plated.transform[Tree[Int]] {
    case b: Branch[Int] => b
    case Leaf(data) => Leaf(data + 1)
  }(tree)
}

Here we are taking advantage of the Plated class from Monocle. Plated allows us to instruct Monocle how to traverse over a recursive data structure. This is similar to how a Lens tells Monocle how to interact with product types and Prism does the same for sum types.

The hard part of this fundamental is defining the Plated instance for Tree. Once we have this, the solution is very simple. We match on the Tree and add one to the data if we find a Leaf. So the main focus for us here will be to understand the definition of the Plated instance for Tree.

An instance of Plated can be created by supplying an instance of another class called Traversal. Traversal is a type that instructs Monocle how to apply a function f to every item inside of our recursive Tree data structure. These instructions are provided to Traversal in the form of a function called modifyF. Let's zoom in on modifyF and talk about each part.

def modifyF[F[_]: cats.Applicative](f: Tree[A] => F[Tree[A]])(s: Tree[A]): F[Tree[A]] = s match {
  case Tree.Leaf(d) => Tree.Leaf(d).pure[F].widen
  case Tree.Branch(d, l, r) => cats.Applicative[F].product(f(l), f(r))
    .map(res => Tree.Branch(d, res._1, res._2))
}

Type Bounds + Applicative

[F[_]: cats.Applicative]

This part of the function is defining a polymorphic higher-kinded type F that is required to have an Applicative instance defined for it. This is really an advanced Scala concept and if you are new to it, it is okay if it doesn't make full sense to you. The best way to break it down is to think of F as being a type that takes another type in its constructor. Examples of this are List, Option, Future, IO, etc. All of these types, when you define them, require you to supply another type. For example, List[String] is a List of type String. Without supplying String, you don't have a complete type. F is just a generic form of this. F could be a List, an Option, etc.

The only constraint that we are putting on F is that it needs to have the behaviors required of an Applicative. Applicative is a scary word and it takes some time to get a good feel for how it works (we are going to have a future Scala Monthly about this). That being said, for now just realize that Applicative is a type class that defines certain behaviors that other types may have.

In this specific example, we are using two functions that Applicative defines, pure and product.

Transformation Function (f)

(f: Tree[A] => F[Tree[A]])

f is the function that we wish to apply to each member of our recursive data structure. As you can see, this function takes in a Tree and returns an F[Tree]. This is so that we have more flexibility over what we do with this function. If the function were just from Tree to Tree then we would be limited to using very simple transformation functions that performed no purely-functional effects.

Current Tree Item

(s: Tree[A])

s is the part of the overall Tree structure that we are currently operating on (Remember that `Tree's are made up of sub-trees).

Return Type

: F[Tree[A]]

Here we are returning an F[Tree] since we are applying the function F which has the same return type.

Leaf Case

case Tree.Leaf(d) => Tree.Leaf(d).pure[F].widen

When we encounter a Leaf node, it is the base-case of our recursion. We don't need to apply f to this Leaf because we already apply f to the l and r of every Branch (as we will see in the next section). This is where Applicative#pure comes in. We need to be able to return an F[Tree], but we only have access to a Tree here (Leaf actually). Luckily we can take our Leaf and lift it into F without modifying it by using the pure function. The only other thing here is a call to widen which is just to signal to the compiler that our Leaf should be treated as a Tree.

Branch Case

case Tree.Branch(d, l, r) => cats.Applicative[F].product(f(l), f(r))
  .map(res => Tree.Branch(d, res._1, res._2))

The most significant thing here is the call to Applicative#product. Product is a function that manipulates product types (tuples) and how they relate to the effect F at hand. In other words, product is a function that takes (F[A], F[B]) and turns it into F[(A, B)]. In this case, we want to apply the function f to the left and the right sides of this Branch. Since f returns an F[Tree], we need a way to get the result of calling f on the left and right and then combining it into a single F[Tree].

Wrapping Up Fundamentals

There are several advanced concepts that we covered in this section. If there is something that didn't make sense to you, please reach out on Discord. It is also recommended that you do some reading on higher-kinded types, Applicative, and the other concepts we covered in these fundamentals. If you found any of the concepts particularly challenging, let me know so I can make a future scala monthly about it.

Challenge

Here is the solution that I came up with for the challenge this month. There are many ways to complete this challenge, and this is just one of them. If you have a different solution, reach out and share it on Discord.

Challenge Part 1

Given a Dream instance representing all possible Dreams that could be encountered, insert the given idea into the dream whose id is equal to destinationDreamId

private implicit val dreamPlated: Plated[Dream] = Plated(
  new Traversal[Dream, Dream] {
    def modifyF[F[_]: Applicative](f: Dream => F[Dream])(d: Dream): F[Dream] =
      d.childDreams.traverse(f).map(res => d.copy(childDreams = res))
  }
)

def inception(possibleDreams: Dream, destinationDreamId: String, idea: Idea): Dream = {
  Plated.transform[Dream] {
    case d if d.id == destinationDreamId => d.copy(idea = idea.some)
    case d => d
  }(possibleDreams)
}

Here we are using Plated just as we did in the fundamentals. There is one new concept here in our use of the traverse function. This function takes, for example, a List[F[_]] and turns it into an F[List[_]]. It is essentially the same thing as the product function we were working with, except it can be applied to types other than product types (such as List, Option, etc).

Challenge Part 2

Given a representation of all possible dreams, the id of an author, and a totem, update all occurrences of the author with the given id to have the new totem rather than their existing one.

private val ideaLens = GenLens[Dream](_.idea).composePrism(some)
private val authorLens = GenLens[Idea](_.origin.author)
private val ideaAuthorLens = ideaLens.composeLens(authorLens)
private val idLens = GenLens[Author](_.id)
private val totemLens = GenLens[Author](_.totem)
private val authorIdLens = ideaAuthorLens.composeLens(idLens)
private val authorTotemLens = ideaAuthorLens.composeLens(totemLens)

def updateTotem(possibleDreams: Dream, authorId: String, totem: Totem): Dream = {
  Plated.transform[Dream] {
    case d if authorIdLens.getOption(d).contains(authorId) => authorTotemLens.set(totem)(d)
    case d => d
  }(possibleDreams)
}

Here we are just combining everything we learned in the fundamentals. We are composing lenses and prisms and using them inside of a Plated#transform call.

Conclusion

Monocle (and the many other optics libraries in Scala) make working with purely functional data much simpler. At first glance, it may seem like Lenses, Prisms, and Plated instances are more effort than they are worth. This can be true if you really only need to use the optic in a singular spot in your application. Like anything, deciding to use optics is about trade-offs. However, if you have a significant amount of transformation code operating on the same data types, optics will save you a lot of complexity. You will only need to define your optics in a single spot and then you can rely on them all through your application.