Practice is one of the best methods of learning a new language and its idioms. Since HackerRank recently released a new category problems, Functional Programming, I decided to learn Scala by first studying its functional aspects.

Although the problems are easy, introductory problems still have potential to demonstrate good practices as I've learned. The language was pleasantly concise and expressive as Python is in terms of its anonymous and higher-order functions. However, the distinguishing features (and the highlights of this post) are Scala's method invocation conventions and the placeholders.

This post will explore effective use of Scala-specific features as well as good practice learned from introductory-level problems. I assume that the reader is familiar with closely-related programming language such as Python or Java and is vaguely familiar with notions such as anonymous functions and higher-order functions.

HackerRank Problem Structure

For each problem, the solution has the same structure. The solution structure can be broken into two sections: the solution implementation and the parsing/printing code. The programmer writes the former and HackerRank handles the latter; subsequently, they offer method headers to be implemented.

object Solution extends App {
    // Solution implementation
    // Parsing/printing code
}

When an object uses the App trait, its body becomes an executable entry point similar to the standard main() method in Java.

Only the problem-specific solution implementations will be presented in this post. We can now begin solving problems.

Introductory Problems

The necessary Hello World problem shows us the structure for a function in Scala. One important convention is that curly braces around the body of a function are optional (and frequently frowned upon) for one-line implementations.

Hello World

We simply print "Hello World".

def f() = println("Hello World")

Here, we use the handy printing function, println(). The only noteworthy aspect is that it is more convenient to type than Java's System.out.println().

Hello World N-Times

We simply print "Hello World" $n$ times.

def f(n: Int) = for (i <- 1 to n) println("Hello World")

Intuitively, we would use a for-loop for this problem. Scala calls the for structure a for-comprehension because of its added capabilities.

Within the for-comprehension, there is a convenience method, to. This convenience method is an easy way to generate a range of values, inclusive, $[1, n]$. This is similar to Python's range(); however, the final value is included in Scala's convenience method.

List Operation Problems

This second set of problems highlights common list operations.

Array of N-Elements

The problem is to generate an arbitrary list of a given size.

def f(num: Int) : List[Int] = List.fill(num)(1)

The List object can generate a list with $n$ repetitions of an element, $e$, using the List.fill(n)(e) method.

Update List

The problem is to transform the negative elements of a list to positive elements. The greater issue is to realize that the lists in Scala are immutable.

Immutable objects in a functional programming language mean that the data structure cannot modify its contents. For example, a Scala list is non-modifiable once it has been defined.

def f(arr: List[Int]) : List[Int] = arr map (x => math.abs(x))

Since we cannot transform the elements of the original list, we must construct a new list. Methods for constructing new lists from existing lists are called transformers. map is a transformer that applies a function to every element of the original list. Hence, we simply apply the math.abs() function to every element to yield a new list with only positive values.

The x => expression syntax defines an anonymous function in Scala. Anonymous functions are functions without a name and are frequently used in higher-order functions for brevity. This is similar to lambda x: expression in Python. Although interesting, this subject is beyond the scope of this post and I will pursue it no further.

Higher-Order Function Problems

An education on functional programming is incomplete without higher-order functions. Higher-Order Functions are those functions which take functions as parameters or return functions. That is, they treat functions as first-class citizens. The map transformer in the previous problem is also a higher-order functions by this definition.

Filter Array

The objective of this problem is to filter out undesired elements in a given list. Intuitively, we use the filter transformer method to construct a new list without the undesirable elements.

def f(delim: Int, arr: List[Int]): List[Int] = arr filter (_ < delim)

The filter transformer, by convention, should be used in in-fix notation as shown in the code example. This is a method invocation convention that is equivalent to arr.filter(...).

The _ in the code is known as a placeholder. Effectively, the placeholder expands to an anonymous function in the tighest scope. In this case, it expands to x => x < delim. The placeholder is a nifty and concise feature of Scala.

Sum of Odd Elements

The problem is self-descriptive (like the others): sum every element of the list that is odd. Simply, we should filter the list to only include odd elements and then use the sum() method on lists.

def f(arr: List[Int]): Int = 
     (arr filter (x => math.abs(x % 2) == 1)).sum

If you have noticed here, we did not use the placeholder:

Effectively, the placeholder expands to an anonymous function in the tighest scope.

By the tightest scope we mean to say that if we used a placeholder

math.abs(_ % 2) == 1

it would expand to

math.abs(x => x % 2) == 1

which is not what we want. Subsequently, it is necessary in this case to explicity write the anonymous function and its parameters.

List Replication

The problem is to replicate each element of the list $n$ times where $n$ is given. Here, we introduce another higher-order function that is not necessarily a transformer, foldLeft.

def f(num: Int, arr: List[Int]): List[Int] = 
    arr.foldLeft[List[Int]](List())
        ((acc, x) => acc ++ List.fill(num)(x))

foldLeft has its counterparts in other functional programming languages such as Lisp and Scheme, but it always has the same structure. The first argument is the starting value, $s$; the second argument is the binary function literal, $f$, that operates on a running accumulator and an element of the list. Subsequently, it is parameterized as follows: foldLeft(s)(f). The fundamental idea is that, for every element in the list, we apply a function to it and append/concatenate to the accumulator value which is initially set to the value of $s$.

In our case, we generate a list of repeated elements for each element in the original list. Then, given the lists of repeated elements, concatenate them together.

List Length

The problem is to compute the length of a given list without using the builtin size() method. Trivially, we should use the foldLeft method again to simply add 1 to our accumulator for each element in the list. The accumulator should start at 0.

def f(arr: List[Int]): Int = 
    (0 /: arr)((acc, _) => acc + 1)

Where is the foldLeft? Well, it turns out that the /: operator is a shorthand expression of foldLeft where the lefthand operand is the starting value and the righthand operand is the list that it operates on. Furthermore, the function literal argument is adjacent to this operator in its own argument list as before.

Fancy Higher-Order Function Problems

These problems utilize higher-order functions with a few fancy tricks on the side. Namely, the fancy tricks are views and prepending.

Filter Positions in a List

Again, we filter elements of the list; however, this time, we must filter them by their index. That is, we remove the element if it has an odd index (which is an even-index since the list is 1-indexed in the problem). The greater problem is that we must zip the original list with its indices much like enumerate() in Python. In Scala, the method for this is zipWithIndex()

def f(arr: List[Int]): List[Int] = 
    (arr.view.zipWithIndex filter (_._2 % 2 == 1) map (_._1))
        .force.toList

zip is a function that takes two lists, $A$ and $B$, and produces a new list where each element is a tuple $(a_i, b_i) \in A\times B$ such that $i$ denotes the index of the element in the corresponding lists.

Zipping the list naively will result in two iterations through the list which inherently doubles the running time, so we use views. A view is simply a lazy proxy for any collection that enables lazy evaluation with transformers. By the lazy evaluation, the zipping is deferred until the filter and map transformations are applied such that only iteration through the lists is necessary.

Lazy evaluation is another popular topic in functional programming similar to anonymous functions. Briefly, it is a method for delaying evaluation of an expression until necessary.

Note that the _._1 and _._2 refer to the first and second components of the tuple constructed by the zipping operation.

Reverse a List

We must reverse a list without using the builtin reverse() method.

def f(arr: List[Int]): List[Int] = 
    arr.foldLeft[List[Int]](List())((acc, x) => x :: acc)

Because the operation is again mutational, we must utilize a transformer. Particularly, we choose the foldLeft transformer. Here, we mimic a pseudo-stack data structure where we pop the head off of the current list and push it onto the stack. The result is an implicit reversal of the elements.

Mathematical Application Problems

These problems are no longer intended for simple introductions. Now, Scala may be applied functionally using all of the learned features. I leave it to the reader now to judge the best approach to each problem. I post my solutions for comparison.

Evaluating $e^x$

The problem here is to approximate the value of a transcendental function, $e^x$, using a series.

def factorial(n: Int): Int = (1 to n).product

def f(x: Float): Float = 
    (List.range(0, 10) map (e => math.pow(x, e) / factorial(e)))
        .sum.toFloat

Area under Curves and Volume of Revolving a Curve

Another approximation application where the problem is calculating discrete integrals over two and three dimensions.

def f(coefficients: List[Int], powers: List[Int], x: Double): Double = 
    (coefficients.view zip powers map (e => e._1 * math.pow(x, e._2))).sum

def area(coefficients: List[Int], powers: List[Int], x: Double): Double = 
     math.Pi * math.pow(f(coefficients, powers, x), 2)

def summation(
    func: (List[Int], List[Int], Double) => Double,
    upperLimit: Int,
    lowerLimit: Int,
    coefficients: List[Int],
    powers: List[Int]): Double = 
    math.floor(((lowerLimit * 1000) to (upperLimit * 1000) 
             map (e => func(coefficients, powers, e * 0.001) * 0.001)).sum * 10) / 10

Conclusion

Although these problems in HackerRank are intended as an introduction into functional programming, there is still room to apply relatively advanced concepts such as higher-order functions and anonymous functions and exploiting Scala-specific idioms. Scala has also shown concise and expressive syntax for functional programming. If you would like to continue learning Scala, keep practicing.

We will continue exploring Scala by completing the HackerRank Recursion subcategory for Functional Programming.