Scala Job Interview – FP questions

writing mathematics school music

Welcome to the third installment of the Scala Job Interview Questions series. This time I’ll try to answer functional programming questions, likely my score will be a bit less than the first two editions (General Questions and Language Questions) because I like Functional Programming, but I’m still a traditional programmer (imperial?) who studied Algebra at high school and uni and then consider Algebra as useful (for programmers) as a doorstop in a tent.

Young and foolish I was, but who could imagine, back then that to run the dance of the bits I would ever need monoids?

Let’s not waste other time in void introduction, and start with the questions and my answers.

What is a functor?

If you are a C++ programmer like me, then the term “functor” pops up the C++ definition of the term. I don’t know exactly why the C++ standardization committee chose this term for naming classes and structs providing the operator(), i.e. a functor is an object that can behave like a function.

Unfortunately, this is wrong and this notion is completely useless in functional programming.

Luckily, like many other exotic concepts in FP, a functor can be explained in terms of interface – A functor is an object that exposes the map method.

More precisely, the functor is composed of a container and some contained items of the same type. The map function allows you to transform the contained items while preserving the structure of the container.

Consider a list of integers, by providing a function that converts integers to strings (e.g. toString) to map, you will get a list of strings.

val a = List( 1, 2, 3 )
val b = a.map( _.toString ) // b is List( "1", "2", "3" )

I wrote “transform”, but in fact, you can map onto the same type, e.g. doubling numbers in the list.

Note that by providing the identity function to map, you’ll get the same container you started with (well another container equal to the original to be more precise).

Up to now, I referred to the external shape of the functor as a container, but in fact, functions can be considered functors as well, since we can map their result. This is equivalent to composing the function with the function passed to the map method.

This post on functors (with javascript) helped me to shed some light on the subject.

When considering the functor as an interface, it may be tempting to write the corresponding Scala trait. This proves not really straightforward –

trait Functor[A] {
  def map[B]( f: A => B ) : Functor[B]
}

Say class C[_] extends from Functor[A], then C[A].map must return C[B], which is not a constraint expressed by the above code. You can have a bit more precise trait by stating that inheritance must be involved with the code:

trait Functor[A] {
  type Self[B] <: Functor[B]
  def fmap[B](f: A => B): Self[B]
}

But still, this does not force the constraint. You can get around this limitation in the Scala trait expressivity, by using type classes (the code is taken from this answer on StackOverflow):

trait Functor[F[_]] {
  def fmap[A, B](f: A => B)(v: F[A]): F[B]
}

// then for each functor you want to treat via the above trait
// define an implict object like this (defined for Option)

implicit object OptionFunctor extends Functor[Option] {
  def fmap[T, U](f: T => U)(v: Option[T]): Option[U] = v match {
    case Some(r) => Some(f(r))
    case None => None
  }
}

What is an applicative?

Applicative is a special kind of functor. As a functor, the applicative wraps a value. When you have two applicatives of the same kind, then you can apply a function that takes the values and produces a new applicative with the result of the function. Generally speaking, you can apply an n-ary function to n wrapped parameters.

In an equivalent way, you can apply a function wrapped in a context to a value wrapped in a context.

Now, while the Scala standard library is full of Functors and Monads (see below), I can find no Applicatives. In fact, it seems that applicative usage is somewhat less common than functors and monads. Anyway, I found an interesting application. In this video, the Validated class from cats library is presented.

The case is simple, suppose you want to validate a form composed of several fields. If you use Either then you can compose all fields validation in a single for comprehension. This is convenient to write, but not that convenient for the user who is reported with the first failed validation and not all the failed validations:

def validateField1( s: String ) : Either[List[String],Field1] = ???
def validateField2( s: String ) : Either[List[String],Field2] = ???
def validateField3( s: String ) : Either[List[String],Field3] = ???

for {
  field1 <- validateField1( str1 )
  field2 <- validateField2( str2 )
  field3 <- validateField3( str3 )
}
yield Form( field1, field2, field3 )

Suppose all three fields are invalid, the for “stop” evaluating at the first field. Now you can write your special version of Either that accumulates errors. On the other hand, you can use the applicative Validated from the cats library.

Validated can replace Either almost everywhere but in the for comprehension. Why? Because only monads can enter the for comprehension and Validated lacks the flatMap method that all monads have.

Instead of for comprehension, there are some alternatives, the most expressive (at least for my taste) is the following:

def validateField1( s: String ) : Validated[List[String],Field1] = ???
def validateField2( s: String ) : Validated[List[String],Field2] = ???
def validateField3( s: String ) : Validated[List[String],Field3] = ???

val result = (
  validateField1( str1 ),
  validateField2( str2 ),
  validateField3( str3 )
).mapN( Form.apply )

What is a monad?

Up to some time ago if you looked up “monad” on the internet you got something on the line “A monad is a monoid in the category of endofunctors…”. It made me cry until I found a site where monads were expressed in programmer-friendly terms.

Basically, a monad is an interface that provides two methods – the first named “pure” (or sometimes “unit”) is used to build the monad out of a value of any given type. The second named “bind” (or “flatMap”) transforms the monad into another monad that has the same structure, but a content computed from the original content.

More precisely if you have a monad wrapping a type A, say Monad[A], then its flatMap has a single argument of type function with the signature: (A) => Monad[A].

The option is a simple monad that allows you to perform computations automatically handling null values. In programming terms, you can represent an Option with a list of either zero or one element. The former is the null value, the second an actual value.

val a = Some(3)
val b = a.flatMap( Some( _.toString ))

By using Some(3) you can create a monad wrapping Option around integer 3. By using flatMap you can convert Option[Int] into an Option[String]. Note that flatMap requires a function returning an Option[], so that the function may also return no value (None).

What are the monad axioms?

There are two axioms – associativity and the existence of the identity element. Being a special case of Monoids, Monads are subjected to the same axioms.

What Scala data type are, or behave like, monads?

There are quite a number of monads in the Scala library: List, Map, Future, Option, Either. BTW, this is a bit too short as an answer, OTH the question is quite closed. I expect the interviewer to take this answer and deepen some aspects, maybe something like – which is your favorite and why.

What are the basic and optional requirement/s to conform a Monad?

Monads need two methods – pure and bind. That is the constructor and the flatMap. These methods must conform to the following laws (I used “Pure” as the name of the constructor method) –

  • left identity: Pure(x).flatMap(f) <=> f(x)
  • right identity: Pure(x).flatMap(Pure) <=> Pure(x)
  • flatMap associativity: Pure(x).flatMap( y => f(y).flatMap(g)) <=> (Pure(x).flatMap(f).flatMap(g)

But… maybe I didn’t get the question O:-)

Explain higher order functions

In functional programming languages, functions are first-class citizens, that is you can use a function much in the same way you use a value. So you can assign a function to a variable and you can pass it to a function as a parameter or get a function back as a return value from a function.

Focus on this – a function that deals with other functions as they would be plain data. That’s a kind of special idea, so special that grants a special name to this class of functions – higher-order functions. map, flatMap, filter are all higher-order functions.

From the programmer’s point of view, there’s nothing more than this, once you know how to declare the type of a function either as parameter or return value, that’s all.

What is gained from using immutable objects?

Immutable objects have several advantages, mainly concurrent programs. In fact, an immutable object never changes, and two threads that access such object, do not need synchronization primitives, since they cannot “write” and both see the same value.

In mathematical terms, once you bound a symbol to a value, there is no way to change the value. You can’t force 3 to be 4. So immutable objects help to reason about the code using mathematical tools.

Some optimizations are available since relying on immutable objects we can assume that object values do not change because of interleaving function calls. I.e. object a is bound to A, then I call f(), when the execution returns from f, a is still bound to the same A it was earlier. This allows the optimizer to move evaluations around the code and simplify the resulting executable.

On the other hand, immutable objects may stress the virtual memory if many objects are created and kept alive for a short time, e.g. in a transformation.

What is tail recursion?

A function that as its last statement calls itself is termed tail-recursive.

How does it differentiate from common recursion?

A recursive function calls itself directly or indirectly anywhere. E.g. recursive implementation of the Fibonacci sequence has two calls to itself.

Some recursive functions may be transformed into tail-recursive functions, but this is not always possible.

Why would you want to perform a similar transformation? Because tail recursion is automatically optimized in a loop.

What issues are there with tail recursive functions in the JVM?

Not sure about the right answer here. Maybe the JIT is capable of detecting a tail recursion and turning it into a loop, but it seems a bit too sophisticated as something to be performed by the JIT.

If the tail recursion is not optimized into a loop, then it may cause a stack overflow.

How does the Scala compiler optimize a tail recursive function?

I guess that the compiler turns the tail-recursive function into a loop. This has the advantage of avoiding stack allocation for each call and the overhead caused by the function call.

How do you ensure that the compiler optimizes the tail recursive function?

You need to add the @tailrec annotation. This is usually a good idea, so that you get notified if, for any reason, you accidentally edited a tail-recursive function in a standard recursive function, with a bad impact on performance.

What is function currying?

Currying is a nice functional trick that allows the programmer to group parameters together. Aside from keeping the argument list tidy, you may want to group parameters together to better leverage implicit parameters or to have a pass a function with more parameters than the function expected as a parameter from another function.

That’s a bit vague, so let’s say you have a sort function that accepts a comparison function:

def sort[A]( array: Array[A], lessThan: (A,A) => Boolean ) : Array[A]

That’s a definition of sorting function perfectly fine and adequate when you need to sort integers or floats, but what if you need to sort text? Text ordering is likely to depend on the locale. So you can write your comparison function as:

def lessThan( l: Locale )( a: String, b: String ) = ???

The double list of parenthesis (but it could be any number you want) is what is called currying, and it fits in the sorting function like this:

sort( array, lessThen( new Locale( "it.IT" ))

Technically the curried function is like a combined function definition. If you invoke the function with only the first group of arguments, then the curried function returns a function that accepts the second group of arguments.

What are implicit parameters?

Implicit parameters are what Odersky has removed from Scala 2 to make Scala 3 :-).

In Scala 2, implicit parameters are used for providing functions with common arguments, without requiring the programmer to explicitly type such parameters every time. As such implicit parameters behave much like controlled global variables.

Implicit parameters in OOP are those values that a method can access, without them being listed in the method parameter list. Notably, these are the member variables of the class to which the method belongs (ignoring for a while inherited stuff).

In Scala, you may specify one or more parameters to be implicit, and then provide an implicit value in the calling context that matches the type of the implicit parameter. When you invoke the function you don’t need to specify the implicit values (you can, if you want, but it is not required).

What are typeclasses?

I had to look up this, but the matter is pretty clear. Typeclasses are a way to wrap existing and closed classes into a package that can be used for operations that the wrapped class was not equipped for.

Let’s get clear of Monads and Monoids that are usually chosen for examples on the subject. Consider you are designing some algorithm that works on the hash code, but the hash code you need has some requirements that are not fulfilled by the standard hash method (yes, the example is stupid, but bear with me for a while).

Now you could write an inheritance wrapper for every class you want to use with the container, but that would be unpractical. The solution is the type class. In Scala, there is no specific construct since you can use the trait –

def trait Hasher[T] {
  def hash( t: T ) : Int
}

val myStringHash : Hasher[String] = new Hasher[String] {
  def hash( s: String ) : Int = s.length
}

Note that I just create an instance of a Hashable for the String. Now we need to propagate this instance to the location where it is used. We can use the implicit mechanism such as in the following code:

class MyContainer[T] {
  def put( t: T )( implicit hasher: Hasher[T] ) : Unit = {
    ???
  }
}

// ...

val mc = new MyContainer[String];
implicit val hashers: Hasher[String] = myHashes.myHashedString
mc.put( "abc" )

Conversely, you could put all hashers in an object as implicit val and then import the object.

This answer took me quite a while to formulate because the idea is pretty simple, but I’m not that fluent.

What are lenses?

Lenses are a functional programming solution to a problem created by functional programming itself 🙂 (this is from my former boss and friend Andrea).

In FP we like unmutable data. This has several advantages as already pointed out, but when you need to update data to evolve the state, you need to make a copy modifying only what has to be modified.

If data are plain, it is not a problem. Consider the following example:

case class User( name: String, role: Role, home: String )

val user = User( "John Smith", Role.GUEST, home: "/guest" )

now the user logs in and you want to change his/her role to Role.ADMIN. Just invoke the copy method in this way:

val user1 = user.copy( role = Role.ADMIN )

When you have a nested and complex data structure, it may be not so straightforward to update data in this way. Using lenses you can actually describe the transformation to apply to the data.

Now, this is a general theory, the specific optics (there are lenses and prisms) require much more space to be presented adequately. I found pretty clear this post on optics in Scala.

What is and which are the uses of: Enumerators, Enumeratees and Iteratee?

This is another hard functional question, I have no idea of the answer. After some googling (in fact, I use duckduckgo), I found the Wikipedia definition for Iteratee. It is a quite convoluted entry (as many that deal with FP, so it is likely that these entries sound hairy to me for my lack of a solid FP background).

All these items are not in the standard Scala library but are available in Play (apparently discontinued since it no longer appears in more recent versions of the library) and Scalaz, and their goal is to provide a functional way to process files. Input data is abstracted away from the file concept and the associated resources and can be composed via the free monad mechanism.

I wouldn’t cheat pretending to be an expert and explaining stuff just hastily looked up on the web.

Conclusions

This section was harder for me to answer. My score would be 11/18, just an incentive to apply more (more applicative you could say).

With my practical, hands-on approach, I managed to get accustomed to mapping and flatmapping around, I found the monad concept, at least in the basic version, useful, but I still have some road to go to properly grasp and employ category theory libraries (cats and scalaz, just to name two).

Next installment will be on reactive programming, stay tuned.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.