Scala with Cats: Answers to revision questions

I'm studying the 'Scala with Cats' book. I want the information to stick so I am applying a technique from 'Ultralearning' where I make revision notes in the questions which I regularly review. This post contains the questions and their answers.

Chapter 1: Introduction: Answers

1. What is a type class? 
• It’s a way of defining some behaviour that many types can adhere to. In scala it's a trait with a parameter
2. What is an interface syntax in cats?
3. What do Show and Eq do in cats? 
• Members of show can be presented as strings. 
4. Explain covariance, contravariance and invariance. 
• Covariance
• Contravariance
• Invariance
F[A] and F[B] are never subtypes of each other, regardless of the relationship between A and B.

Chapter 2: Monoids and Semigroups: Answers

1. Define monoid and semigroup and give examples of each. 

Chapter 3: Functors: Answers

1. What is a type constructor? 
• A type constructor is like a type but it has a 'hole to fill'. Eg List is a type constructor because it has one 'hole' to fill. Note the difference between List (a type constructor) and List[A] (a type, using a type parameter) and List[Int] (a concrete type).
2. What  is a  covariant functor? 
3. Write a method 'power' which can operate on either List(1,2,3) or Option(2) and returns List(1,4,9) and Option(4) respectively. 
4. What is a contravariant functor? 

Chapter 4: Monads

1. What is a monad? 
2. What is the 'Id' monad for? 
• Imagine you have a method which operates on a Monad of Ints, eg power method so for Option(2) it returns Option(4) and for List(1,2) it returns List(1,4). To use this method on regular ints we need to wrap our plain Ints in a monad, hence Id. 
3. What is the 'Eval' monad for? 
• This is for abstracting over different modes of computation, eager or lazy. Memoized computations run once then are cached, and can run lazily or eagerly. vals are eager and memoized. Defs are lazy and non memoized. Lazy vals are lazy and memoized. Eval has three subtypes, Now, Later and Always. 
• It also has 'defer' which can be used to avoid stack overflow in recursive methods.
4. What does each line print? 
• 'Now' is eager and memoized (val). 'Later' is lazy and memoized (lazy val). 'Always' is lazy and not memoized (def). 
5. What is the output of the following code snippet and why? 
• "Now" is calculated eagerly so is printed first. However mapping functions are always called like defs so the output is 'a, ---, b, c, Adding!, b, c, Adding!' There is a memoize function that can be used when chaining. 
6. What is the writer monad for?
• This is for carrying a log along with some computation. It's particularly useful in multithreaded computation where normal log messages might get interleaved. Writer[W,A] has a log of type W and a result of type A.
7. What is the reader monad for? 
• Reader[A,B] represents a function A => B. It allows sequencing of operations that depend on some input. 
8. What is the state monad for? 
• The state monad allows us to pass additional state around as part of a computation. We can use it to model mutable state in a purely functional way, without the mutation. State[S, A] represents functions of type S => (S, A). S is the type of the state and A is the result type. 

Chapter 5: Monad Transformers

1. What are monad transformers used for? 
• These are for composing monads, eg for giving us nice ways of handling Future[Option[T]]

Scala with Cats: Revision Questions

Earlier this year I read a fantastic book about Ultralearning. One tip from the book was to make notes in the form of questions without the answers rather than making notes to browse. Therefore, to review my work I can answer the questions and test my recall rather than just reading information and hope it goes in. 

The answers are in another post. 

Chapter 1: Introduction

1. What is a type class? 
2. What is an interface syntax in cats?
3. What do Show and Eq do in cats? 
4. Explain covariance, contravariance and invariance. 

Chapter 2: Monoids and Semigroups

1. Define monoid and semigroup and give examples of each. 

Chapter 3: Functors

1. What is a type constructor? 
2. What is a covariant functor?
3. Write a method 'power' which can operate on either List(1,2,3) or Option(2) and returns List(1,4,9) and Option(4) respectively. 
4. What is a contravariant functor? 

Chapter 4: Monads

1. What is a monad? 
2. What is the 'Id' monad for? 
3. What is the 'Eval' monad for? 
4. What does each line print? 
5. What is the output of the following code snippet? 
6. What is the writer monad for?
7. What is the reader monad for? 
8. What is the state monad for? 

Cake pattern

(don't read this post if you are eating because it might make you throw up)

Partial Unification

Writer Monad from Scala Cats

Once upon a time there was some stinky side affecting code with println all over the place.


How horrible! No, Cinderella, you definitely can't meet the prince of MonadLand looking like that!
Fortunately her Functional Fairy Godmother is on hand.



 'Ah ha' she cries! From each function you need to return both the int (which is the existing return type) and some Strings to represent the logs!

'Easy peasy' she says and with a swish of her magic wand she transforms Cinderella.

Well I guess this is ok, but look how much more effort Cinderella has to go to to compose f and g! That's not very elegant at all!

'Please, Fairy Godmother', Cinderella begs, 'Isn't there anything more you can do?'

Now it's a little-known Disney secret that Cinderella's Functional Fairy Godmother is actually an enormous fan of Cats and has a clever Writer monad trick up her sleeve.

Output:

WriterT((Vector(Generating random int, Applying complex mathematical formula),84))
WriterT((Vector(Generating random int, Applying complex mathematical formula),84))

'Oh thank you Functional Fairy Godmother', cries Cinderella, delighted.

FFG winks and whispers, 'I just love a good for comprehension! There are actually a lot of different ways of creating a writer!', and she slips some example code into Cinderella's pocket for later bedtime reading, in case things with the prince don't go to plan:

Cinderella was so intrigued by these examples that she stayed up all night reading Dave Gurnell and Noel Walsh's book Scala with Cats and skipped the ball entirely.


And she lived happily ever after. 

Varience in scala

Seriously I never remember which is which.

Covariance

Contravarience

Invariance

Akka Persistence: From Untyped to typed

Vanilla Akka Persistence

Akka persistence involves three main concepts:

- Commands
- Events
- State

Consider the following two command objects:

case class WriteCommand(data: String)
case object PrintCommand

We are going to build an actor which responds to two sorts of commands 'Write!' and 'Print!'. When it receives a WriteCommand, the data in the command will be persisted and when it receives a PrintCommand it will print all the saved data to the console.

On receipt of a WriteCommand our actor will generate and persist a WriteEvent.

case class DataWriteEvent(data: String)

The actor will maintain an internal representation of the data it has persisted  ('state') . This is the data that will be printed to console on receipt of a PrintCommand.

The state has an update method which is called with a DataWriteEvent. The updated state is returned.

case class ExampleState(events: List[String] = Nil) {
  def updated(evt: DataWriteEvent): ExampleState = copy(evt.data :: events)
  def size: Int = events.length
  override def toString: String = events.reverse.toString
}

Wiring up the actor:

class ExamplePersistentActor extends PersistentActor {
  override def persistenceId = "example-id"
  var state = ExampleState()

  def updateState(event: DataWriteEvent): Unit = state = state.updated(event)

  def numberOfEvents: Int = state.size

  val receiveCommand: Receive = {
    case WriteCommand(data) ⇒
      persist(DataWriteEvent(s"$data-$numberOfEvents")) { event ⇒
        updateState(event)
        context.system.eventStream.publish(event)
      }
    case PrintCommand ⇒ println(state)
  }

  val receiveRecover: Receive = {
    case evt: DataWriteEvent ⇒ updateState(evt)
    case SnapshotOffer(_, snapshot: ExampleState) ⇒ state = snapshot
  }

}

And finally to run:

object Example extends App {
  val system = ActorSystem()
  val actor = system.actorOf(Props(new ExamplePersistentActor))
  actor ! WriteCommand("Ruby")
  actor ! PrintCommand
}

If I run it once I get the following:

List(Ruby-0)

And running it one more time:

List(Ruby-0, Ruby-1)

Moving on...

Receive is a function with a signature from Any => Unit which is pretty damn generic! Akka typed, the motivation for which is beyond the scope of this post, basically gives compile-time feedback on the correctness of your actor interactions. 

Sexy Types

This time we define a 'behaviour' in terms of Command, Event and State. This means that we need our 'Write!' and 'Print!' commands to share a type hierarchy: 

sealed trait TypedExampleCommand extends Serializable
case class TypedExampleWriteCommand(data: String) extends TypedExampleCommand
case object TypedExamplePrint extends TypedExampleCommand

Our event and state look pretty much the same as they did before:

case class TypedEvent(data: String)

case class TypedExampleState(events: List[String] = Nil) {
  def updated(evt: TypedEvent): TypedExampleState = copy(evt.data :: events)
  def size: Int = events.length
  override def toString: String = events.reverse.toString
}

 Our behaviour is defined with four parameters:

1. An id for the actor

2. An initial state

3. A function for converting commands to events (wrapped in 'Effects') and handling side effects

4. A function for updating the state given an event

object TypedExample {

  def behavior: Behavior[TypedExampleCommand] =
    PersistentActor
      .immutable[TypedExampleCommand, TypedEvent, TypedExampleState](
      persistenceId = "example-id", 
      initialState = new TypedExampleState,      
      commandHandler = PersistentActor.CommandHandler {
        (_, state, cmd) ⇒
          cmd match {
            case TypedExampleWriteCommand(data) =>
              Effect.persist(TypedEvent(s"$data ${state.size}"))
            case TypedExamplePrint =>
              println(state); Effect.none          
        }
      },     
      eventHandler = (state, event) ⇒ event match {
        case TypedEvent(_) => state.updated(event)
      }
    )
}

Now to run it:

object TypedExampleMain extends App {

  import akka.actor.typed.scaladsl.adapter._

  val system = akka.actor.ActorSystem("system")
  val actor = system.spawn(TypedExample.behavior, "example")
  actor ! TypedExampleWriteCommand("Hi Bella")
  actor ! TypedExamplePrint
}

Again running once gives:

List(Hi Bella 0)

And twice:

List(Hi Bella 0, Hi Bella 1)

Typed vs Untyped

Let's define a case object: 

case object FluffyKittenFace 

If we send a FluffyKittenFace message to our persistent actor then the message gets swallowed. The original code continues to work but nothing appears to happen. 

However if we try sending a FluffyKittenFace to our typed actor: 

Red squiggle of doom! 

We helpfully get a compile time error saying that our actor doesn't know what to do with all that fluff! 

FluffyKittenFace is going to have to find another actor to process her message, or become a TypedExampleCommand. 

Zee Cod:

https://github.com/polyglotpiglet/akka-typed-examples

Note that these examples are working against master rather than the release build. It should work from 2.5.9. 

NoVisibility.java example in Java Concurrency in Practice

I've been going through Java Concurrency in Practice and trying to reproduce the examples as I go through.

I found that when trying to illustrate the no visibility problem in chapter 3 the example in the code didn't work for me so I tweaked it a little bit:

Here is the test:



Then after running it for some time:

org.junit.ComparisonFailure:
Expected :0
Actual   :-1822446613

\o/

Are you smarter than a pigeon?

I went to a talk on Monday at the Royal Institution entitled 'Are you smarter than a chimpanzee?' During this talk the lecturer referred to the Monty Hall problem and cited a study where university students played the game show and had to choose whether to stick or switch their choice of door.

Counterintuitively, switching improves your chances of winning from 1/3 to 2/3 but the university students tended to stick with their choice rather than switch, and therefore they didn't win very much. Part of this is because it's counterintuitive that switching would win and also because we humans are very loss averse. We prefer better to have chosen the wrong door and stick to it than to have chosen the winning door and give it up.

I wrote a little script which runs the Monty Hall problem and indeed around 66.6% of the time, switching will make you win.

The interesting thing from the talk is that apparently pigeons have played this game and unlike the university students, they learned very quickly that if they switch they improve their chances of winning, ie the birds outperformed the students.

How cool is that?

Functional Definitions: Monoid, Functor, Monad

Monoid

Functor

Monad

Memory alignment: Oops and viewing mem structure with Jol

Why are 32-bit machines limited to 4GB memory? 

On a 32-bit machine there are only 2^32 (~= 4 billion) distinct memory addresses.

Each memory address can hold 8 bits (= 1 byte).

That means that in total we can reference ~ 4 billion bytes which is approximately equal to 4 GB.

In practice, all of this memory won't be available to the JVM. Some of it will be used by the OS and any other processes running on the machine. Even less will be available to the heap because the JVM needs to store lots of other things including thread stacks, GC info, native memory, compiled code etc.

So 64-bit machines are the solution? 

64 bit machines can reference 2^64 memory addresses which is more than 16 million terabytes of data. Therefore, it should be fine for a Java heap right?

The problem with this addressing is that you end up with huge pointers to objects that you have to store in the heap! The addresses suddenly take twice the amount of memory, which isn't terribly efficient.

What if you don't actually want a multi-terabyte heap? Is there some kind of middle ground?

The middle ground: Compressed Oops

Imagine we have 35-bit addressing. That would mean that we could store up to 2^35 (~= 32GB) memory addresses in heap.

Wouldn't that be great?! Obviously it isn't going to be easy because there aren't any 35-bit machines with 35-bit registers in which to hold memory addresses.

However, the JVM can do something very clever, where it assumes that is has a 35 bit number but the last 3 bits are all zero. When it writes to the memory address it adds the three zeros to lookup the address correctly but when it's just holding the memory address, it only stores 32 bits.

However this means that the JVM can only access every 8th memory address:

000 (0), 1_000 (8), 10_000 (16), 11_000 (24), 100_000 (32), 101_000 (40) etc

This means that the JVM needs to allocate memory in 8-byte chunks (because each memory address holds 1 byte and we are dealing with the memory addresses in chunks of 8).

However this is how the JVM works anyway, so it's all fine and nothing is lost. Convenient, eh?

There is a little bit of fragmentation. If you allocate an object that is 7 bytes then you have 1 empty byte but the impact isn't too big. Though this is probably why we don't try and use 2^36 addresses. That would mean being 16-byte aligned which would likely have much worse fragmentation and wasted memory gaps.

When does the JVM use Compressed Oops? 

From Java 7 onwards, by default if the heap size is >4GB but <32GB then the flag,  +XX:UseCompressedOops is switched on.

Jol

To see how objects are aligned in memory, Jol is a cute little tool.

Example 1:

import org.openjdk.jol.info.ClassLayout;import org.openjdk.jol.vm.VM;import static java.lang.System.out;
public class Jol {
    public static void main(String[] args) throws Exception {
        out.println(VM.current().details());        out.println(ClassLayout.parseClass(A.class).toPrintable());    }
    public static class A {
        boolean f;    }
}

Gives the following output:

# Objects are 8 bytes aligned.
# Field sizes by type: 4, 1, 1, 2, 2, 4, 4, 8, 8 [bytes]
# Array element sizes: 4, 1, 1, 2, 2, 4, 4, 8, 8 [bytes]

com.ojha.Jol$A object internals:
 OFFSET  SIZE    TYPE DESCRIPTION                    VALUE
      0    12         (object header)                N/A
     12     1 boolean A.f                            N/A
     13     3         (loss due to the next object alignment)
Instance size: 16 bytes
Space losses: 0 bytes internal + 3 bytes external = 3 bytes total

We can see that the object header took 12 bytes, the boolean took 1 byte and 3 bytes were wasted

Example 2 (Same as above but add in a little integer)

import org.openjdk.jol.info.ClassLayout;import org.openjdk.jol.vm.VM;import static java.lang.System.out;
public class Jol {
    public static void main(String[] args) throws Exception {
        out.println(VM.current().details());        out.println(ClassLayout.parseClass(A.class).toPrintable());    }
    public static class A {
        boolean f;        int j;    }
}

Output:

# Objects are 8 bytes aligned.
# Field sizes by type: 4, 1, 1, 2, 2, 4, 4, 8, 8 [bytes]
# Array element sizes: 4, 1, 1, 2, 2, 4, 4, 8, 8 [bytes]

com.ojha.Jol$A object internals:
 OFFSET  SIZE    TYPE DESCRIPTION                    VALUE
      0    12         (object header)                N/A
     12     4     int A.j                            N/A
     16     1 boolean A.f                            N/A
     17     7         (loss due to the next object alignment)
Instance size: 24 bytes
Space losses: 0 bytes internal + 7 bytes external = 7 bytes total

JIT Fun Part 4: Intrinsics and Inlining

Definition: Intrinsic

Intrinsic methods in Java are ones that have a native implementation by default in the JDK. They will have a Java version but most of the time it will get inlined and and the intrinsic implementation will be called instead.

Note that what methods are made intrinsic may depend on the platform.

Examples of Intrinsic methods include Math functions (sin, cos, min, max). The full list is here.

Example

Code:

We run this method with the following jvm flags:

-XX:+UnlockDiagnosticVMOptions -XX:+PrintInlining

In the output we see the following:

 @ 97   java.lang.Math::max (11 bytes)   (intrinsic)

Woohoo! It got inlined with the intrinsic code. 

JIT Fun Part 3: -XX:PrintCompilation

Ok enough guessing about these graphs. Let's look at what's really happening.

But first...

Compiler levels

Level	Compiler
0	Interpreter
1	C1 and destined to stay in C1 forever
2	C1 but only pays attention to loop/method counters
3	C1 but gathers details for C2 eg counters, percentage of time conditional evaluates to true
4	C2

Paths through these levels:

0 -> 3 -> 4

• This is the most common case. Method initially sent to C1 level 3 after a fair few calls, then if it is called a lot or contains a loop with lots of iterations it gets promoted to the super fast level 4 (= C2).

0 -> 3 -> 1

• This happens if the method is really tiny. It gets sent to level 3 where it is analysed and we realise that it will never go to C2 so we stick it into C1 level 1 forever.

0 -> 2 -> 3 -> 4

• If C2 is busy at the time of promotion from level 0 then we know we won't get promoted for a while so we go hang out in level 2 rather than hopping off to 3 directly. Then we may get promoted to 4 if we deserve it. 

Example

I've got the following code:

And the times (endTime - startTime) look like this:

I ran the code with -XX:PrintCompilation and I'm using Java 8 so tiered complation is enabled by default.

Let's see what is happening to the rawr method:

90
    164  171 %     3       com.ojha.Rawr::main91 @ 50 (131 bytes)

What does this mean?

i (ith iteration of my for loop which is on the x axis) = 90
timestamp since vm start = 164
this method was 171st in the queue to be compiled
% indicates on stack replacement (method contains a loop)
3: This is the most important bit! This means we are moving into C1, ie doing the first compilation.
50 is the bytecode index of the loop.

More output

159
    167  176       3       com.ojha.Rawr::main (131 bytes)

231
    169  172       3       java.io.PrintStream::ensureOpen (18 bytes)
    169  182 %     4       com.ojha.Rawr::main @ 50 (131 bytes)

At i = 231, the loop has been called enough times for the Rawr main method to be compiled at C2 (that's what the 4 means). Note that at the same time java.io.PrintStream.ensureOpen has been called enough times to be compiled at C1 level 3.

1818
    3       com.ojha.Rawr::main @ -2 (131 bytes)   made not entrant

This is basically saying that the level 3 version of the rawr method shouldn't be used any more (correct because we should now use the level 4 version). We can see this dip in the graph at x = 1818.

1999
    193  234   !   3       java.io.PrintStream::println (24 bytes)
    193  182 %     4       com.ojha.Rawr::main @ -2 (131 bytes)   made not entrant

At the very end of the method Rawr main is over so the level 4 version of the compiled code is made not entrant (ie nothing should 'enter' or call that compiled code).

Note that the ! indicated that the method contains a try catch loop. 

JIT Fun Part 2: Throwing the JIT a curve ball

This post follows on from the previous post about visualising JIT.

Let's start with a simple, silly main method:

Plotting the elapsed time in ns:

We can see that:

Up to about the 70th run it is running in the interpreter
Then it drops into C1 until 200
At 200 it optimises again into C2

At 600 it hits our curve ball and deoptimises the method.
Method eventually drops back in C2 at around 800.

Curve ball:

The compiler thought that our String curveBall was always going to be null and it added that into the compiler. However, when we set it to something other than null the compiler realised that it has made a wrong assumption and had to deoptimise that compiled method. 

JIT Fun Part 1: Quick JIT visualisation of tiered compliation

See the following code:
It's not doing anything exciting, just running the same inner loop 1000 times.

I have taken those times and put them in a file called 'output.txt'.

See the following python function which reads in the numbers from output.txt and plots them on a graph:

Here is the graph that it produces:

At first the code is running in the interperter, then the C1 JIT, then it settles into the C2 JIT. A couple of spikes probably indicate GC.

vcsh with myrepos (mr)

VCSH

Vcsh allows you to maintain multiple git repos in one directory. I use this for having separate git repos for dot config files that live in my home directory.

Setting up a new vcsh git repo for a a dot config file (eg .vimrc)

vcsh init vim

vcsh vim add ~/.vimrc

vcsh vim commit -m "first commit"

vcsh vim remote add origin git@github-personal:polyglotpiglet/vim.git

On github created a new repo called 'vim'

vcsh vim push -u origin master

vcsh vim push

MyRepos (MR)

I have several such vcsh repos. Wouldn't it be nice to bulk pull updates for all these repos? Or bulk check them out? 

With mr you define a ~/.mrconfig file which lists all the repos to manage.

I added the following configuration parameter to my git config:

git config --global push.default matching

This means that 'mr push' works. Mr push does 'git push' on each of the repos and by setting this config param it means that you push to the remote branch with the same name as the local branch by default. 

Java 8: Parallel Streams - Performance with ArrayList vs LinkedList

Consider the following function:

 public static int sum(List<Integer> values) {
    return values.parallelStream().mapToInt(i -> i).sum();
 }

It's using java 8 parallel streams to sum a list of Integers.

In this post we will demonstrate and explain the difference in the performance of this function when passing in a LinkedList vs an ArrayList.

Generate the lists to be tested

The following code creates an IntStream of random Integers.

 Random random = new Random();
 int n = 10000000;
 Stream<Integer> stream = IntStream.range(0, n)
        .map(i -> random.nextInt())
        .boxed();

Collect it into a list:

 List<Integer> list = stream.collect(Collectors.toList());

Here there are no guarantees about type (though it's probably an ArrayList) so let's create two lists, one LinkedList and one ArrayList.

 ArrayList<Integer> al = new ArrayList<>(list);
 LinkedList<Integer> ll = new LinkedList<>(list);

Benchmark

Cheeky little wrapper function to add the timing: 

 public static long timedSum(List<Integer> values){
    long startTime = System.nanoTime();
    sum(values);
    long endTime = System.nanoTime();
    return endTime - startTime;
 }

Note: Do not do benchmarking like this. Instead use JMH. I'm just a bad bad person. 

Running the Code

Let's run the code a few times for each type of list and take the average time (after a warm up, of course). 

 System.out.println("ArrayList " + 
        new Double(LongStream.range(0, 5)
                .map(i -> timedSum(al))
                .average()
                .getAsDouble()).intValue());
 System.out.println("LinkedList " + 
        new Double(LongStream.range(0, 5)
                .map(i -> timedSum(ll))
                .average()
                .getAsDouble()).intValue());

Results

ArrayList   17907140
LinkedList 160238673

The ArrayList performs about x10 better than the LinkedList. 

Analysis of Results

Parallel streams use a fork/join model when they execute. This means that the task is split into subtasks. Each subtask is executed and the results combined. In this example, the list is partitioned and each partition is summed. These partitions are then summed until we have one final answer. 

Clearly, this partitioning will be most effective when the partitions are roughly equal.  An ArrayList supports random access, so partitioning is much quicker and easier than with a LinkedList; decomposing the list into these partitions is O(n). 

Java 8: Diamond Inference for methods

As of Java 8, we don't need to specify the types when we pass in typed parameters.

 public static void main(String... args) {
    operateOnHashMap(new HashMap<>()); // empty diamonds :D 
 }
 static void operateOnHashMap(Map<String, Integer> map) {
    // do stuff with map
 }

Java 8: Functional Interface

Definition: 

A function interface in java is an interface with a single abstract method. They are used to type lambda expressions.

Example: 

In the following example, 'Cat' is a functional interface.

 interface Cat {
    void meow();
 }

 public static void main(String... args) {
    Cat cat = () -> System.out.println("Meowwwwww");    
    cat.meow();
 }

It is good practice to annotate functional interfaces with the annotation @FunctionalInterface .

Java 8: Runnables with Lambdas

Old (anonymous inner classes)

 Runnable meow = new Runnable() {
    @Override    
    public void run() {
        System.out.println("meow");    
    }
 };
 meow.run();

Output: 
    meow

    Process finished with exit code 0

New.1 (lambda)

 Runnable rawr = () -> System.out.println("rawr");
 rawr.run();

Output: 
    rawr

    Process finished with exit code 0

New.2 (passing function call)

 public static void main(String... args) {
    Runnable lalala = Main::LaLaLa;    
    lalala.run();
 }

 public static void LaLaLa() {
    System.out.println("lalala");
 }

Output: 
    lalala

    Process finished with exit code 0