Simple Tasks and a Functional Blonde Approach

A couple of months ago, I made a commitment to self-education. In other offices there is such a topic - an employee, they review them once a half a year and say, “come on to the next review, you will learn Spring, patterns (what?) And functional programming!” The idea would be nice if the goals were not set so blurry. Let's skip the spring and patterns for the weekend - I rushed to attack the AF.

Of course, I had general, vague information about the FP - I can write anonymous classes in Java - I am familiar with the similar capabilities of Python and JavaScript.

I'll start with simple exercises on the Scala, I decided. I chose Scala because we have Java as the main working tool - well, there were also variants of Clojure, Groovy and Java8 (something else?) - but maybe I will try with them later.

I set goals for myself (did I understand the AF correctly?):

• Solve tasks in a functional style
• Those. if possible, do not use explicit loops and branches
• And also avoid mutable collections, etc.

Some exercises were easy, others to put it mildly not very. Now I will try to briefly talk about this - to streamline new knowledge. It is difficult to say whether this article can help someone in the future, or rather, someone will help me myself by pointing out errors or suggesting improvements.

Summation and Filtering

The very beginning - rock downloading and googling in search of "how to start Main" I will skip. Managed - and okay.

As a first example, the first task with ProjectEuler is to count the sum of those numbers from 1 to 999 that are divisible by 3 or 5. In general, it looks like FizzBuzz.

Google helped me find examples of range generation and filtering:

object Main extends App {
    def res = (1 to 999).filter(x => x % 3 == 0 || x % 5 == 0)
    System.out.println(res.sum)
}

However, I wrote and thought about it: I use a ready-made range task - and a ready-made summation function. I vaguely remembered aggregating functions and after ten minutes I rewrote the sum using reduce (I remembered it from Python). And how to generate a list of numbers from 1 to 999? After about an hour of torment, I gave birth to a recursive function (sorry, I could not without it).

import scala.annotation.tailrec
import scala.collection.immutable.Vector
object Main extends App {
    @tailrec
    def genList(sz: Int, res: Vector[Int]): Vector[Int] = {
        if (sz == 0) res else genList(sz - 1, sz +: res)
    }
    def res = genList(999, Vector()).filter(x => x % 3 == 0 || x % 5 == 0)
    System.out.println(res.reduce((a, b) => a + b))
}

Of course, I won’t do this anymore - we believe that if I know how to write some kind of library function, I can use it.

UPD
After a hint in the comments I realized that I can use the stream for generation (which I met later) - thanks for the kick in the right direction:

    def list = Stream.iterate(1)(x => x + 1).takeWhile(x => x < 1000)
    def res = list.filter...

Input and Output

Entering one number from the console was not difficult. For an example, I chose one of the old problems - triangular numbers . You need to answer whether the entered number is triangular or not. I created a list of triangular numbers in an ugly way and then checked if there was anything entered in it, but I mastered the map function (with which I am familiar mainly from JavaScript).

import scala.io.StdIn
object Main extends App {
	def tris = (1 to 500).map(n => n * (n + 1) / 2)
	val x = StdIn.readLine.toInt
	System.out.println(if (tris.contains(x)) "YES" else "NO")
}

It does not work out without branching at all - I reassure myself that they are small.

What if you need to enter a lot of numbers? I took the exercise of summing up several pairs of numbers. First comes the number of pairs, and then in separate lines the pairs themselves.

I got a more general task - I need to find the amount in each row (optional for a pair):

import scala.io.StdIn
object Main extends App {
    val n = StdIn.readLine.toInt
    val samples = Iterator.continually(StdIn.readLine).take(n).toList
    val output = samples.map((x) => x.split(" ").map(_.toInt).sum)
    System.out.println(output.mkString(" "))
}

I decided another five similar problems - to count in a cycle, transform, output - until I got tired.

Streams and iterations “before lunch”

I still remember Collatz’s hypothesis from some kind of children's book - then I spent almost a day checking it on a piece of paper for the number 97 (I didn’t succeed). Having found the corresponding task, I thought that I would crack it quickly, but in fact I mastered it only the next day.

At first I wrote with a recursive function (similar to what I did above), but then I began to look for some more ready-made approach. Thanks to this, I met with Stream, iterate and takeWhile.

So, the line contains numbers - you need to calculate how many iterations the Collatz transformation for each of them will lead to unity:

import scala.io.StdIn
object Main extends App {
    def collatz(a:Long) = if (a % 2 == 1) a * 3 + 1 else a / 2
    val input = StdIn.readLine.split(" ").map(_.toLong)
    val output = input.map(m => Stream.iterate(m)(collatz).takeWhile(_ > 1).size)
    System.out.println(output.mkString(" "))
}

It turned out so short that I already thought that I was ready for any troubles. However, a couple of exercises later, I was faced with a real disaster.

Simple Numbers

I have become accustomed to generating primes (mainly using the same exercises with ProjectEuler from the time I learned Java) using trial division. It suddenly turned out that in a functional form it is (at least to me) very difficult to write. Indeed, in a cycle, you need to check more and more new numbers, adding them to the resulting array, which at the same time this check is going on ...

Here's the task - to print prime numbers with the corresponding serial numbers at given indices. I thought that it was only necessary to generate an array - and hurray ...

Having spent half a day, I already undertook to browse the Internet in search of clues. Unfortunately, freaks like this "one-liner" not only did not bring me closer to a solution, but on the contrary strengthened the feeling of my own inferiority.

In the end, I won by inventing a recurrence function, where the list of already found numbers and the next verified number is passed. Here is this monster:

def generate(n: Int) = {
    @tailrec
    def mainLoop(test: Int, found: Vector[Int]): Vector[Int] = {
        if (found.size == n) {
            return found
        }
        mainLoop(test + 2, if (found.find(test % _ == 0).nonEmpty) found else found :+ test)
    }
    mainLoop(3, Vector(2))
}
val values = StdIn.readLine.split(" ").map(_.toInt)
val primeList = generate(values.max)
val output = values.map(x => primeList(x - 1))
System.out.println(output.mkString(" "))

I had shorter solutions, but they worked satisfactorily for numbers less than a hundred - their speed obviously suffered due to implicit internal iterations ...

I do not like what happened. I found some apparently scientific article on the generation of primes in a functional style, where, it seems, it is hinted that for AF it is preferable to try the approach with the sieve of Eratosthenes. However, I still feel weak enough at Scala to come up with how to fill the sieve immutably. Although now - right while I was writing this text - it occurred to me that I needed to use something like an immutable HashSet.

I hope that by the time I mature to write about the continuation of my experiments (if this is relevant) I will have a better solution.

Conclusion

On this I dare to thank you for reading about my misadventures. I wrote about them first of all because those several tutorials on AF that I came across for some reason carefully showed me examples that are easy to write in a functional style - and avoided those from which the brain swells.

If you notice other exercises - simple in appearance, but not very simple to implement in a functional form (at least for a beginner) - please share them!