DEV Community: Stefan Compton

How To Become a Millionaire Scala Developer

Stefan Compton — Fri, 29 Apr 2022 11:56:09 +0000

Or, Simple Web API with Http4s and Cats Effect

"The EuroMillions lottery gives you a 1 in 140 million chance of not going to work tomorrow. With alcohol it's 1 in 5." - Anonymous

OK, I'm unlikely to get any "thank you" messages from Millionaires, but if you follow this post then there is a sense in which you will become a millionaire. If our physicists are right. And for a given meaning of become.

Getting All Quantum

So, the set up is this. We use a quantum random number generator, which then splits the universe in 140 million or so worlds, and...

Wait, Splits the Universe?

According to the most austere and plain reading of quantum mechanics, any quantum event which we perceive as probabilistic, is not really - all eventualities actually happen, none of them is a special real eventuality, and it's just our parochial view on the world that only permits us to see one outcome.

So given all that, we use a quantum random number generator, create all those universes and guarantee that a version of me (or you) will win the lottery.

Enough Theory, Let's Get Coding

The first thing I did was create a service for getting random numbers. The class RandomService takes a function that for a given number will generate that many random numbers. I'm using the Cats Effect IO monad to wrap the calculation, as I don't want to immediately evaluate it. Since the call will be to a front end API, and it in turn wants to call the back-end API, I don't want to run any of it explicitly synchronously.

class RandomService(randomFunction: Int => IO[Seq[Int]])

I'm generating randoms in the service, then using them to perform a Fisher-Yates shuffle. If you ask for 5 numbers from 1-50 then it will generate all numbers from 1-50 and take 5 of them.

def generateNumberSequence(numberGroup: NumberGroup): IO[Seq[Int]] = {
    randomFunction(numberGroup.size).map(rands => {
        val result = shuffle(1 to numberGroup.size, rands)
            .take(numberGroup.count)
        if (numberGroup.isFullList) result else result.sorted
    })
}

@tailrec
final def shuffle(values: Seq[Int], randoms: Seq[Int], index: Int = 0): Seq[Int] = {
    val n = values.size
    if (index == n - 1) values
    else shuffle(swap(values, index, index + (randoms(index) % (n - index))), randoms, index + 1)
}

@tailrec
final def swap(seq: Seq[Int], i: Int, j: Int): Seq[Int] = {
    if (i == j) seq
    else if (j < i) swap(seq, j, i)
    else seq.take(i) ++ Seq(seq(j)) ++ seq.slice(i + 1, j) ++ Seq(seq(i)) ++ seq.drop(j + 1)
}

the NumberGroup is just a data type to carry the magnitude of numbers requested and how many of them. Note that we sort the numbers you request except when the group is full - if you request all numbers from 1-50 then the order is important, you don't just want 1,2,3 ... 50!

The other interesting part is the web service Lotto

trait Lotto {
  def generate(vals: Seq[NumberGroup]): IO[Lotto.Response]
}

object Lotto {
  final case class Response(nums: Seq[(Int, Seq[Int])])
  val randomService = new RandomService(QRNG.f)
  object Response {
    implicit val lottoEncoder: Encoder[Response] = (resp: Response) =>
      Json.obj(
        ("Your Numbers:",
      Json.fromFields(resp.nums.map(t => (t._1.toString, t._2.asJson)))
        )
      )
  }

  def impl: Lotto = (vals: Seq[NumberGroup]) => {
    val resp = vals.map(randomService.generateNumberSequence).sequence
    resp.map(r => Response(r.zipWithIndex.map(t => (t._2, t._1))))
  }

I love the straightforward declarative nature of the code. Also how concise it is. Most of the complexity is in getting the response to look OK. It still needs some work though!

Notice also the .sequence method that takes a sequence of our IO monads and sequences them into one IO. Conceptually it's reorganizing the result without having to perform the computation. Nice!

All that's left is to run our Http4s server, which couldn't be simpler.

  def run: IO[Nothing] = {
    val lottoAlg = Lotto.impl
    val httpApp = QuantumMillionaireRoutes.lottoRoutes(lottoAlg).orNotFound
    val finalHttpApp = Logger.httpApp(logHeaders = true, logBody = true)(httpApp)
    EmberServerBuilder.default[IO]
        .withHost(ipv4"0.0.0.0")
        .withPort(port"8080")
        .withHttpApp(finalHttpApp)
        .build
  }.useForever

And there it is. All the code is on my GitHub here

And when you do become a Millionaire, please let that version of me know - if I know him, he'll put it on his CV ...

LazyList And Memoization

Stefan Compton — Sun, 24 Apr 2022 17:29:02 +0000

“Progress isn't made by early risers. It's made by lazy men trying to find easier ways to do something.” ― Robert Heinlein

One of the benefits that Scala (and other functional programming languages) have over their imperative brethren is the concept of lazy evaluation. Lazy evaluation doesn't evaluate a computation in it's entirety, but simply computes what is absolutely required when and only when it's required.

The LazyList, introduced in Scala 2.13 (see Stream for 2.12 and before) is an immutable linked list implementation that is evaluated lazily. Elements are only computed as needed.

Consider a list from 0 to infinity. With a regular List, we couldn't declare this, as it would need to be fully evaluated, which would never terminate. But with the LazyList we can just say

val list = LazyList.from(0)
val list: scala.collection.immutable.LazyList[Int] = LazyList(<not computed>)

Note that none of this list has been evaluated. Intuitively we know that this list is non-empty, but if we try to find out we get

val empty = list.isEmpty
val empty: Boolean = false

list
val res1: scala.collection.immutable.LazyList[Int] = LazyList(0, <not computed>)

So, in attempting to determine if the list is empty, the head had to be calculated. And once calculated it now has a concrete (immutable) value. Any further attempts to get the head will return that now-computed value.

This property of the LazyList, known as Memoization, is extremely useful, and to see why let's take a look at a classic example of recursion - calculating Fibonacci numbers.

Fibonacci

Consider the classic Fibonacci function, here recursively in Scala

def fib(n: Int): BigInt = {
  if (n == 1) 0
  else if (n == 2) 1
  else fib(n - 1) + fib(n - 2)
}

This vary simple implementation has 2 base cases, then recursive calls to calculate fibonacci in terms of descending values until we reach the base case. But, there's a big problem with this naive implementation. Calculating fib(n) will cause calls to fib(n-1) and fib(n-2). In turn these will generate calls to fib(n-2), fib(n-3), fib(n-3), fib(n-4) and so on. By the time we get a few levels deep, we're calculating the same values over and over again. Running the above function to calculate fib(40) on my Macbook Air takes about 4 seconds, and fib(50) almost a minute. Add to this that there are a lot of non-tail recursive calls and the possibility of a stack overflow, should you have the patience to await termination.

Clearly all of that is an issue for a relatively straightforward problem.

Enter memoization and LazyList

The Scala docs for LazyList gives a nice single line implementation of fib as

val fibs: LazyList[BigInt] =  BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map{ n => n._1 + n._2 }

We can see the base values at position 0 and 1 being populated with the LazyList cons operator #:: We then have subsequent values calculated by zipping all fibs with fibs.tail and the next fib number is the sum of these two. Because it is lazily evaluated we can zip an indefinitely long sequence with its tail. And memoization ensures that the concrete value of any given position is only calculated once.

Using this I was able to compute in a few seconds that fib number 100,000 has 20,000 digits. Nice.

fibs.take(100000).lastOption.foreach(n => println(n.toString.length))
> 20899

None of this comes for free, however, and the trade off, as usual, is in memory space. In the above example, a linked list of size 100,000 must exist in memory, and will continue to do so while there is a reference to the head in scope (val fibs).

If you are given to trying out competitive programming, or assessment sites like TopCoder or Hackerrank, then you are sure to come across Dynamic Programming (DP). Memoization is a technique of DP that will get you through many auto-graded assessments, and for that reason alone is worth learning. Plus it gives us a new way to look at old problems, and that's always worthwhile.

Either In Scala

Stefan Compton — Sat, 23 Apr 2022 10:57:18 +0000

“Either is both, and Both is neither.” - Plutarch

Either is another of scala's monadic types that it might be easy to overlook when first learning the language. However, I think it combines a lot of the rationale for Scala and also Scala (and FP) idioms, and is therefore worth taking the time to become familiar with.

As a monadic type, the purpose of Either is to allow you to compose computations in a declarative, functional style.

But What Is An Either?

Either is a wrapper type for a value that can be one of two types. Suppose I want to write a method that divides two numbers. If the division succeeds then I want to return a double. If it fails, I want to return a String with a message.

In Java we can't really do this.

// can't do this
public *what?* method(int num, int denom) {
    if (denom == 0) {
        return "cannot divide by 0";
    } else {
        return (double)denom / num;
    }
}

We could throw an exception, and let the calling code then catch it and decide what to do

public double method(int num, int denom) throws IllegalArgumentException {
    if (denom == 0) {
        throw new IllegalArgumentException("cannot divide by 0");
    } else {
        return (double)denom / num;
    }
}

...

// calling code
try {
    double res = method(1, 0);
    doSometh(res);
} catch (IllegalArgumentException iae) {
    doSomethElse(iae.getMessage());
}

While this example is meant to be trivial and not something you'd want to do, there are a number of issues with the Java implementation imho.

it's verbose (well it is Java I suppose!)
semantically the string path has to be an exception condition - this is mostly OK as it's likely what you want to use this kind of code for.
IllegalArgumentException is correct from the method pov, but from the calling code it doesn't make much sense. The message it wraps is not unambiguously related to illegal arguments, it's just a different value that was returned from the method.
exceptions are side effects

Enter The Either

As previously mentioned, Either wraps one of two generic types. For our toy example above we could use an Either[String, Double] and the code would look like

def method(num: Int, denom: Int): Either[String, Double] = {
    if (denom == 0) Left("cannot divide by 0")
    else Right(denom.asDouble / num)
}

...

// calling code
method(1, 0) match {
    case Left(s) => // do something stringy with s
    case Right(d) => // do something doubley with d
}

I think this nicely addresses the concerns with the Java code. It's concise and clear. The two value types are just different paths and not semantically exceptions. In fact we don't need to use an exception just to wrap the String value at all. And there are no side effects.

A More Involved Example

While the above captures some of the aspects of Either, the real power comes when running a number of computations, any of which may fail. Especially when you have Java code you need to be interoperable with that throws Exceptions. The Java model of throwing exceptions doesn't work well in the world of pure, idempotent, side-effect free functions. This is particularly problematic once you get into Akka Actor systems that can span multiple VMs or machines.

Let's take a look at how Either can help us work with Java code in a functional way.

Suppose we have a Java method that likes to throw exceptions

public int unpredictableJavaMethod(int n) {
    if (n % 2 == 0) {
        return n;
    } else {
        throw new RuntimeException("failed");
    }
}

And suppose we have a sequence of values we need to run through this code and evaluate the results

val results = (1 to 10)
    .map(unpredictableJavaMethod)

Unfortunately this will fail with a runtime exception on value 2 and we'll never get to the rest of the results. Rather more fortunately we can wrap our computations in Either like so

def throwableToLeft[T](block: => T): Either[java.lang.Throwable, T] =
    try {
        Right(block)
    } catch {
        case ex => Left(ex)
    }

So now we can just wrap the java call and end up with composable operations like

val results = (1 to 10)
    .map(n => throwableToLeft(js.unpredictableJavaMethod(n)))

results.map {
    case Left(ex) => // do something with exception
    case Right(value) => value
}

Instead of map we can fold over the results if we need to reduce it to a single value. Or filter, or use a Scala for comprehension if that syntax is easier.

Summing Up

So Either is a way of putting two types together in one, but the real power is in the way it supports integrating Java code into your Scala project in a safe and functional way.

Recursion in Scala

Stefan Compton — Fri, 22 Apr 2022 09:20:16 +0000

Recursion

"It's déjà vu all over again." - Yogi Berra

I was in an interview coding test recently, trying to solve a problem in under 5 minutes. The problem was simple enough, some kind of String manipulation, but required a loop to solve it. Since I was working in Scala, and since I believe the best way to work in Scala is the pure functional way (as much as possible), I wrote the loop as a tail recursive function.

Coding Interviews

As an aside, the format of this interview leaves a lot to be desired in my opinion.

Firstly, it is entirely unrealistic in terms of the work I was being assessed to do. When will I ever have 5 minutes to solve a problem? And could anyone trust something thrown together in such haste?
Secondly, the string manipulation in question could be more effectively done with libraries that I was not allowed to use.
Finally, when I asked for some test cases, or info to build test cases in order to start development, I was told there's no time! When you're used to working in a test-first TDD/BDD manner, it's really jarring to be told not to do that. I mean, how would I know what I was writing was remotely correct?

I'll end this extended digression by saying I understand why the interview was conducted like this, it's quick and makes the candidate talk about what they are doing, and there really aren't many great ways to assess a candidate in depth without taking half a day. But it feels like there should be a better way.

Tail Recursion

When the interview was over, the interviewer said they were very impressed with the solution and said they hadn't seen anyone solve this problem with recursion. Now given that the interview was a Scala interview, that perplexed me a bit. Were they writing Java style loops? So I thought I'd dig into recursion a bit and cover why I think my solution with recursion was the right one.

The classic example for looping and recursion is the factorial function. A factorial of number n is defined as

1 * 2 * .... * n

So 5 factorial would be

1 * 2 * 3 * 4 * 5 = 120

Writing this up as a loop is pretty simple. Let's use a Java while loop

public long factorial(int n) {
    long result = 1;
    int i = 1;
    while i <= n {
        result *= i;
        i++;
    }
    return result;
}

This has the undesirable Java-ism of mutable state variables - both i and result are mutated. It also uses a 64 bit long, which will overflow pretty fast. It's probably fine for this toy example, but we can do better in Scala

def factorial(n: Int): BigInt = {
    if (n <= 1) 1
    else n * factorial (n - 1)
}

Great, no mutation, and it's nice and concise. It even uses the BigInt (which wraps Java's BigInteger) for arbitrarily long integers - just as well since factorial of 100 is 158 digits long!

But there's still something wrong. To get a clue what it is, let's try the factorial of 20,000

factorial(20000)
...
Exception in thread "main" java.lang.StackOverflowError
...

Uh oh! We clearly have a problem. A Stack Overflow, no less. To understand the issue, let's take a quick look at our old friend the stack.

The Stack

The Stack is the space in memory where local variables are stored, and it's main purpose is to support function calls. Each call to a function will create a new frame on the stack, and any local variables still in use will occupy that stack frame.

In our example the final line, which gives the formula for a factorial recursively is leaving the value of n on the stack to be used in the final computation. The program will keep making stack frames for n, n-1, n-2 and so on. Since stack space is limited, and the stack frame itself takes up memory, we eventually run out of space and the program halts.

Luckily for us, Scala has support for a stack optimization technique called tail recursion. If you define a recursive function in such a way that nothing is left on the stack and all we have is a final call to the recursive function, then Scala will re-use the same stack frame for each call and thus prevent a stack overflow.

Here's the tail recursive version

import scala.annotation.tailrec

@tailrec
def factorial(n: Int, accumulator: BigInt = 1): BigInt = {
    if (n <= 1) accumulator
    else factorial(n - 1, accumulator * n)
}

The mail difference here is that, rather than leaving n on the stack to be assessed at the end of a number of function calls, we're explicitly calculating an accumulator and passing it along.

And running it allows us to see that factorial of 20,000 has 77,338 digits. Cool!

Note the annotation to say that it's tail recursive. This is a compile time convenience, if the function is changed to not be tail recursive, then you'll get a compile time issue. The compiler will a tail recursive function without the annotation.

So there we are. Recursion is a pretty basic technique in FP and, while you might not use it for exactly these purposes, they are a perfect fit for recursive data structures, like trees and tries.

Monads

Stefan Compton — Tue, 19 Apr 2022 14:45:16 +0000

"It's Just Another Manic Monad" - Susanna Hoffs

There's an old adage in the FP space - as soon as you gain an understanding of monads, you lose the ability to explain them to anyone else.

Fortunately I have a limited understanding, and so hopefully this will allow me to occasionally drift into lucidity.

Rather than diving deep into a ton of stuff about category theory, I want to try a different approach and look at what is a monad in Scala and what that means in practical terms

My god, it's full of monads

Basically anything in Scala that wraps an object (or objects) of another type is a monad. So that mean List, Map and basically all the collection types, Option, Future, Either ... and so on.

Consider a List[String]. It's a monad wrapping 0 or more Strings.

A monad must have 2 operations, one to construct a monad from the wrapped type, and one to apply a function to each of the wrapped value and return a monad of the same type.

The first operation is pretty straightforward - it's the apply() method which, in the case of our List, is sugared as List(x)

The second operation is somewhat more invloved. Known as bind, or in Scala flatMap, it takes a function that operates over the values in the monad and produces a monad of the same type (but with values of a possibly different type).

If we look at the signature of flatMap on List it is (approximately) as follows

def flatMap[B](f: (A) => List[B]): List[B]

Dissecting this we see that flatmap takes a function that outputs a List[B] as it's argument, and returns a List[B]

As an aside, one of the challenges I find with functional programming is that everything is abstracted. I'm sure that method signatures with generic types are enough for some people to grok a new concept, but I need examples with concrete types.

So what does flatmap mean?

Suppose we have a List of recording artists names in the form of Strings, and a function that takes a recording artist name as a String and produces a List of albums they have made.

val recordingArtists = List("The Bangles")
val getAlbums: String => List[String] = ???

recordingArtists.flatMap(getAlbums)  //  List("All Over the Place", "Different Light", "Everything"...

In our example the types A and B are the same type - String, and what flatMap is doing is mapping each value in the input to it's output from function f. It is then flattening the result - hence flatMap.

It's the flattening part that's of interest to us as Scala devs. Let's look at another example via another aside.

One of the things I love about Scala is the lack of null. OK you can use null if you really want to, but I think that's perverse, since we have a few tricks that are way better.

Suppose we have a calculation that may produce a result, or it may not. Maybe you want to look up an artist and the function may return their band if it knows about them or it may not. For this we have the type Option which produces a Some(value) or None

So our function application may look like

f("Susanna Hoffs")   // Some("The Bangles")
f("Stefan Compton")  // None

And suppose we have a variant of our previous function that gets the best album from that band, if they have produced any

val getBestAlbum: String => Option[String]

Now we can use flatMap to compose these functions and get a result

f("Susanna Hoffs").flatMap(getBestAlbum)  // Some("Album Title")

Note that we've done this in a single line that's very clear in intent and meaning and without needing any null checks or the possibility of blowing up with a null pointer exception. I'd call that a result.

All this is really scratching the monadic surface, but hopefully none of it is particularly scary. I shall sign off with a John von Neumann quote, slightly mdified by me to better fit.
“Young man, in ~~mathematics~~ computing you don’t understand things. You just ~~get~~ use ~~d to~~ them.”

Eta Expansion in Scala

Stefan Compton — Tue, 19 Apr 2022 11:10:06 +0000

Eta Expansion

"Can you tell me about Eta Expansion?"

I froze. My pulse raised, temperature started rising, throat dried. I mumbled something about methods and functions and how Scala is OO. But that I didn't know, sorry! Please stop staring.

This was my reaction to a fairly innoccuous question in an interview for a Scala contract. The work never came off. The company apparently wanted to make an offer, alas internal politics interviened. But I can't help thinking it was my lack of a coherent answer to that question that led to my downfall!

Incidentally this is not an untypical reaction that I have in interview situations. Fortunately coding has nothing to do with the instant recall of textbook process descriptions and everything to do with solving problems, but there's not really a good way to test that in a 30 minute interview. So here we are.

This blog is my attempt to put down an actual answer to that question, and in doing so gain some extra insight into Scala and also FP in general.

So what is Eta Expansion?

One of the core tenets of FP is that functions are first-class citizens. If you can do something with a value, then you can do it with a function. Consider the definition of the method map on the List class

final def map[B](f: (A) => B): List[B]

We can see that map on a List[A] takes a function as an argument that will map elements from a type A to type B, and return a List[B]

So we can turn numbers into strings like so

List(1, 2, 3).map(n => n.toString)

So far, so functional. Our anonymous function satisfies the signature of map, which takes a function A => B (or Int => String in this case).

But what if we want to pass in a method. We know that scala is OO and so when we say

def f(n: Int): String = ...

then f is a method on the class we're working in, and not a function. We would define a function as

val f: (Int) => String = ...

And (in Scala 2.x) we can put a function in a List (first class, remember), but not a method

val fFunction: (Int) => String = ...
def fMethod(n: Int): String = ...
List(fFunction) // ok
List(fMethod)   // not ok

(This is not the case in Scala 3, which has improved Eta Expansion to allow this and also add in support of auto-expanding curried functions)

But hang on a sec, my Scala compiler will cheerfully allow

def f(n: Int): String = 
....
List(1, 2, 3).map(f)

And this is where Eta Expansion comes in. Phew! That's a long way to go without touching how it works.

It's worth noting that when we define a function like

val f: (Int) => String = ...

This is syntactic sugar and what's really under the hood is an object which implements the trait FunctionN, or specifically in this case

Function1[Int, String]

And it's associated apply method, which will apply the function to given argument(s).

So there we have it, Eta Expansion somewhat expanded upon. There's lots more to unpack, especially in Scala 3, so I may come back to this in the future.