From F# to Scala – case class/object (ADTs)

Note: read the whole series here.

 

Continuing on from where we left off with traits last time around, let’s look at Scala’s case class/object which can be used to create Algebraic Data Types (ADTs) in Scala.

 

Case Class

You can declare an ADT in F# using Discriminated Unions (DUs). For example, a binary tree might be represented as the following.

In Scala, you can declare this ADT with a pair of case class.

Here is how you construct and pattern match against F# DUs.

This looks very similar in Scala (minus all the comments).

Also, one often use single case DUs in F# to model a domain, for instance…

From what I can see, this is also common practice in Scala (at least in our codebase).

From this snippet, you can also see that case classes do not have to be tied together to a top level type (via inheritance), but more on this shortly.


UPDATE 16/01/2017: as @clementd pointed out, you can turn case classes with a single member into a value class and avoid boxing by extending from anyVal. For more details, see here.


On the surface, case classes in Scala looks almost identical to DUs in F#. But as we peek under the cover, there are some subtle differences which you ought to be aware of.

 

Case Object

In F#, if you have a union case that is not parameterised then the compiler will optimise and compile it as a singleton. For instance, the NotStarted case is compiled to a singleton as it’s always the same.

You can declare this GameStatus with case classes in Scala.

But reference equality check (which is done with .eq in Scala) reveals that:

  • NotStarted() always create a new instance
  • but equals is overridden to perform structural equality comparison

If you want NotStarted to be a singleton then you need to say so explicitly by using a case object instead.

Couple of things to note here:

  • as mentioned in my last post, object in Scala declares a singleton, so does a case object
  • a case object cannot have constructor parameters
  • a case object cannot be generic (but a normal object can)

When you pattern match against a class object you can also lose the parentheses too (see the earlier example in print[T]).

 

Cases as Types

For me, the biggest difference between DUs in F# and case classes in Scala is that you declare an ADT in Scala using inheritance, which has some interesting implications.

As we saw earlier, each case class in Scala is its own type and you can define a function that takes Node[T] or Empty[T].

This is not possible in F#. Instead, you rely on pattern matching (yup, you can apply pattern matching in the function params) to achieve a similar result.

It’s also worth mentioning that, case objects do not define their own types and would require pattern matching.

What this also means is that, each case class/object can define their own members! Oh, and what we have learnt about traits so far also holds true here (multiple inheritance, resolving member clashes, etc.).

In F#, all members are defined on the top level DU type. So, a like-for-like implementation of the above might look like this.

Whilst this is a frivolous example, I think it is still a good demonstration of why the ability to define members and inheritance on a per-case basis can be quite powerful. Because we can’t do that with F#’s union cases, we had to sacrifice some compile-time safety and resort to runtime exceptions instead (and the implementation became more verbose as a result).

The autoPlay function also looks slightly more verbose than its Scala counterpart, but it’s mainly down to a F# quirk where you need to explicitly cast status to the relevant interface type to access its members.

 

sealed and finally

“make illegal states unpresentable” – Yaron Minsky

Ever since Yaron Minsky uttered these fabulous words, it has been repeated in many FP circles and is often achieved in F# through a combination of DUs and not having nulls in the language (apart from when inter-opting with C#, but that’s where your anti-corruption layer comes in).

This works because DU defines a finite and closed set of possible states that can be represented, and cannot be extended without directly modifying the DU. The compiler performs exhaustive checks for pattern matches and will warn you if you do not cover all possible cases. So if a new state is introduced into the system, you will quickly find out which parts of your code will need to be updated to handle this new state.

For instance, using the GameStatus type we defined in the previous section…

the compiler will issue the following warning:

warning FS0025: Incomplete pattern matches on this expression. For example, the value ‘GameOver (_)’ may indicate a case not covered by the pattern(s).

You can also upgrade this particular warning – FS0025 – to error to make it much more prominent.

 

In Scala, because case classes/objects are loosely grouped together via inheritance, the set of possible states represented by these case classes/objects is not closed by default. This means new states (potentially invalid states introduced either intentionally or maliciously) can be added to the system and it’s not possible for you or the compiler to know all possible states when you’re interacting with the top level trait.

There’s a way you can help the compiler (and yourself!) in this case is to mark the top level trait as sealed.

A sealed trait can only be extended inside the file it’s declared in. It also enables the compiler to perform exhaustive checks against pattern matches to warn you about any missed possible input (which you can also upgrade to an error to make them more prominent).

Since case objects cannot be extended further we don’t have to worry about it in this case. But case classes can be extended by a regular class (case class-to-case class inheritance is prohibited), which presents another angle for potential new states to creep in undetected.

So the convention in Scala is to mark case classes as final (which says it cannot be extended anywhere) as well as marking the top level trait as sealed.

Voila! And, it works on abstract classes too.

 

But wait, turns out sealed is not transitive.

If your function takes a case class then you won’t get compiler warnings when you miss a case in your pattern matching.

You could, make the case class sealed instead, which will allow the compiler to perform exhaustive checks against it, but also opens up the possibility that the case class might be extended in the same file.

Unfortunately you can’t mark a case class as both final and sealed, so you’d have to choose based on your situation I suppose.

 

Reuse through Inheritance

Because case classes are their own types and they can inherit multiple traits, it opens up the possibility for you to share case classes across multiple ADTs.

For instance, many collection types have the notion of an empty case. It’s possible to share the definition of the Empty case class.

I think it’s interesting you can do this in Scala, although I’m not sure that’s such a good thing. It allows for tight coupling between unrelated ADTs, all in the name of code reuse.

Sure, “no one would actually do this”, but one thing I learnt in the last decade is that if something can be done then sooner or later you’ll find it has been done 

 

Summary

To wrap up this fairly long post, here are the main points we covered:

  • you can declare ADTs in Scala using case class and/or case object
  • case classes/objects are loosely grouped together through inheritance
  • a case class defines its own type, unlike discriminated unions in F#
  • a case object creates a singleton
  • case classes/objects can define their own members
  • case classes/objects support multiple inheritance
  • marking the top level trait as sealed allows compiler to perform exhaustive checks when you pattern match against it
  • Scala convention is to seal the top level trait and mark case classes as final
  • sealed is not transitive, you lose the compiler warnings when pattern matching against case classes directly
  • you can mark case classes as final or sealed, but not both
  • multiple inheritance allows you to share case classes across different ADTs, but you probably shouldn’t 

 

Links

From F# to Scala – traits

Note: read the whole series here.

 

Continuing on from where we left off with type inference last time around, let’s look at a language feature in Scala that doesn’t exist in F# – traits.

Scala has both abstract classes and traits (think of them as interfaces, but we’ll get into the differences shortly) to support OOP. Abstract classes are exactly what you’d expect and the preferred option where Java-interop is concerned. Traits, however, are much more flexible and powerful, but with great power comes great responsibility.

 

Basics

Like abstract classes, they can contain both fields and behaviour, and both abstract definitions and concrete implementations.

Any class that extends from this trait will inherit all the concrete implementations and need to implement the abstract members.

Of course, the concrete class can also override the default implementation that came with the trait.

You can extend multiple traits.

wait, hold on a sec, what’s this object thingymajig?

Sorry for springing that on you! A Scala object is basically a singleton and is Scala’s equivalent to a F# module. In fact, when you define an object in the Scala REPL it actually says “defined module“!

The notable difference with a F# module is that a Scala object can extend abstract classes and/or traits (but itself cannot be extended by another class/object). We’ll spend more time drilling into object later in the series but I just wanted to throw it in here for now as it’s such a heavily used feature.

The key thing to take away from the snippet above is that you can extend a class or object with multiple traits.

 

Traits vs Abstract Classes

There are 2 differences between traits and abstract classes:

  1. traits cannot have contractor parameters but abstract classes can
  2. you can extend multiple traits but can only extend one abstract class

With regards to point 2, you can actually mix both traits and abstract classes together!

 

Dealing with Collisions

Since you can extend more than one thing at a time (be it multiple traits, or 1 abstract class + 1 or more traits), one must wonder what happens when some of the members collide.

You might have noticed from our last snippet that both Being and Human defines a name field, but everything still works as expected and you can indeed use the theburningmonk object as a Human or Being.

Ok. What if I extend from 2 traits with clashing members and one of them provides a concrete implementation? My expectation would be for the concrete implementation to fill in for the abstract member with the same name.

and indeed it does.

What if I’m mixing traits with an abstract class?

No problem, still works.


side note: notice that in this second version ProfessorX is extending Psychic first? That’s because in cases where abstract class and traits are both involved, only the traits can be mixed in.


So far so good, but what if both traits/abstract classes provide a concrete implementation for a clashed member?

The safe thing to do here would be for the compiler to crap out and force the developer to rethink what he’s doing rather than springing a nasty surprise later on.

(and yes, it behalves the same way if Light or Dark is an abstract class instead)

This, in my opinion is a much better way to resolve collisions than the Python way.

 

Dynamic Composition

So far we have mixed in traits when defining a new class or object, but you can do the same in a more ad-hoc fashion.

Of course, all the rules around collision resolution also hold true here.

 

Generics

Whilst traits cannot have constructor parameters, they can have type parameters (ie, they are generic!).

To sneakily weave in the Transformers game I’m working on at Space Ape Games, here’s how you might model a Transformer Combiner as a generic trait.

 

Stackable Modifications

When you read about traits in Scala, you often hear the phrase “stackable modifications” (Jonas Boner’s real-world Scala slide deck has a nice example).

What makes this interesting (and different from straight up override in inheritance) is how super is modified in an ad-hoc fashion as you compose an object using traits (see Dynamic Composition section above).

This also works if Mutant is an abstract class, and in the definition of an object too.

However, it only work with methods. If you try to override an immutable value then you’ll get a compiler error.

And no, it doesn’t work with variable either, only methods.

 

self type annotation

Another related topic is the so-called self type annotation feature. It is often used to implement dependency injection in Scala with patterns such as the Cake Pattern.

Where you see code such as below (note the self : A => ), it means the trait B requires A.

Any composing object/class would need to mix in trait A if they want to extend trait B, failure to do so will be met with a swift and deadly compiler error.

This also gives the trait B access to members from A (which includes any members A inherits). For instance.

What’s more, you can mix in multiple traits in the self type.

It’s worth differentiating this “requires” relationship from the “is a” relationship created through inheritance.

In this case, since the Rooney trait is not a Footballer and RecordHolder (which he is in real life, of course) it won’t inherit the members from those traits either.

 

Interestingly, it’s possible to create cyclic dependencies using self type

which is not possible through inheritance.

As a .Net developer who have seen the damages cyclic references can do, I’m slightly concerned that you could do this in Scala…

That said, in Martin Odersky‘s Programming in Scala, he has an example of how this mutual dependency can be useful in building a spreadsheet, so I’ll keep an open mind for now.

…a new trait, Evaluator. The method needs to access the cells field in class Model to find out about the current values of cells that are referenced in a formula. On the other hand, the Model class needs to call evaluate. Hence, there’s a mutual dependency between the Model and the Evaluator. A good way to express such mutual dependencies between classes was shown in Chapter 27: you use inheritance in one direction and self types in the other.

In the spreadsheet example, class Model inherits from Evaluator and thus gains access to its evaluation method. To go the other way, class Evaluator defines its self type to be Model, like this:

  package org.stairwaybook.scells
  trait Evaluator { thisModel => ...

 

Finally, as you can see from Martin Odersky‘s example above, you don’t have to use “self” as the name for the self instance.


side note: I’m curious as to how Scala deals with a cyclic dependency where the traits define values that depends on a value on the other trait.

as you can see from all that red, even the code analysis tool in IntelliJ gave up trying to understand what’s going on, but it compiles!

What’s interesting (and again, slightly worrying) is when the fields are evaluated, which actually depends on the order the traits are mixed in.

(new Object with Yin with Yang).motto 

  1. Yin is mixed in, yang.motto is not yet initialised (and therefore null) so Yin.phrase is initialised as null + “yin”
  2. Yang is mixed in, yin.phrase is initialised to “nullyin“, so Yang.motto is now “nullyin” + “yang”
  3. the value of motto is therefore nullyinyang

(new Object with Yang with Yin).motto 

  1. Yang is mixed in, yin.phrase is not yet initialised, so Yang.motto is initialised as null + “yang”
  2. Yin is mixed in, but since motto is already initialised, whatever happens here doesn’t really affect our result
  3. the value of motto is therefore nullyang

ps. please DO NOT try this at work!


 

So, that’s everything I have learnt about traits in the last week, hope you have found it useful in your path to learn Scala.

Until next time, ciao!

 

Links

From F# to Scala – type inference

It’s a new year, a new job, a new language (Scala) and runtime (JVM) to work with.

After a week of learning about my new surroundings at Space Ape Games and getting up to speed with Scala I have learnt a fair bit. In my own journey (aided by Twitter’s Scala School, Odersky’s Coursera course and Effective Scala) I found the target audience for a lot of online materials is Java developers, or developers who are new to functional programming.

As a proficient F# developer, a lot of the FP concepts translate quite easily to Scala (albeit with a different, more verbose syntax). However, Scala does have a lot of language features that do not exist in F# and many things (such as type inference) work slightly differently and can bite you in subtle ways if caught unaware of these differences.

So, for anyone coming into Scala from F#, I hope I can provide some useful info based on the things that I found interesting in my journey.

One of those things is how type inference differs in the two languages.

 

F# uses a Hindley-Milner type inference system similar to its ML brethren, but Scala’s type inference works slightly differently.

Take the following example for instance, this bit of code works just fine in F#.

but the same doesn’t work in Scala…

unless you explicitly specify the type parameter for toList.

Interestingly, if you rewrite the function in curried form then the Scala compiler is able to infer the type for toList.

but the order of parameters matters somehow..

which I eventually understood thanks to some helpful folks on Twitter.

 

Although less restrictive, this limitation of only being able to unify types from left to right also applies to F#.

For example, a simple example using the backward pipe (<|) is enough to cause the compiler to bark.

I hope this has been useful for you, over the next weeks or months I should be adding more posts to this series as I better familiarise myself with Scala, both in terms of language features as well as the toolchain/ecosystem around it.

See here for the rest of the series (as they become available).

Advent of Code F# – Day 25

ps. look out for all my other solutions for Advent of Code challenges here.

 

Day 25

See details of the challenge here.

Today’s input looks like this:

cpy a d
cpy 7 c
cpy 362 b
inc d
dec b
jnz b -2

At last, we’re at the end of this year’s Advent of Code challenges, and today’s challenge is another twist of the assembunny code we’ve seen a few times this year, most recently on Day 23.

Ad before, let’s define the instruction set as a union type and make short work of the parsing the input file.

One notable difference to today’s challenge though is that we’re no longer interested in the value of the registers but the output from executing the program.

So instead of returning the registers we’ll use a sequence comprehension to return the output values as an infinite, and lazy sequence instead.

(ps. I initially wrote the execute function with a nested recursive function, but on second thought the problem feels more concisely expressed as a while loop so I rewrote it as such)

To wrap up today’s challenge (part 2 just requires you to click a link to wrap up your AOC journey for another year) we need to find the first value of n that will yield pairs of [ 0, 1 ] indefinitely. Of course you can’t be sure that the pattern repeats indefinitely without deeper understanding of the pattern of change in the register values (perhaps it’d be a better approach rather than the trial-and-error route I have gone with). I have gone with 1000 values all following that pattern = repeating indefinitely, but turns out the answer is the same even when you use Seq.take 10.

So there it is folks, another year and another set of wonderfully enjoyable challenges. With you all a happy new year and see you soon!

 

Links

Advent of Code F# – Day 24

ps. look out for all my other solutions for Advent of Code challenges here.

 

Day 24

See details of the challenge here.

Today’s challenge is a mix of Breadth-First Search (or Level Order Tree Traversal) and the Travelling Salesman Problem.

First, let’s parse the input file into a 2D array to make it easier for us to work with.

My first attempt at solving this challenge with the same BSF approach that has been so useful in this year’s AOC challenges proved unsuccessful. Unlike previous challenges, today’s problem can involve backtracking so we can’t rely on a naive cache of positions we have passed through thus far.

However, we can still use BSF to find out the shortest distance between any two numbered nodes.

From here, we can build up a dictionary of the distance between every pair of numbered nodes and turn this BSF problem into a Travelling Salesman Problem and find the path through all the numbered nodes with the lowest total distance.

Now we can solve part 1 of the challenge with a simple recursive function.

This solution ran in 109ms on my laptop, including the time to build up the distances between pairs of nodes.

 

Part 2

Of course, if you leave the cleaning robot somewhere weird, someone is bound to notice.

What is the fewest number of steps required to start at 0, visit every non-0 number marked on the map at least once, and then return to 0?

A slight twist on part 1, but we can use the same approach as before but simply stipulate that when all numbered nodes have been traversed we also take into account the distance from the last node back to number 0.

This ran in 113ms on my laptop, including the time to build up the distance between pairs of nodes (or, 14ms if reusing the existing pairDistances)

 

Links