Simple Tasks and Functional Blonde Approach

A couple of months ago I made a commitment to self-education. There is such a topic in other offices - an employee, they review every six months and say “let's see the Spring, patterns (what?) And functional programming for the next review!” The idea would be nice if the goals weren't so vague. Let us skip the spring and patterns so far - on the weekend I rushed to the attack on the OP.

I certainly had general information about the FP — I know how to write anonymous classes in Java — I know Python and JavaScript with similar abilities.
')
I'll start with simple Scala exercises - I decided. I chose Scala because the main working tool we have is Java - well, there were other variants of Clojure, Groovy and Java8 (something else?) - but I'll try with them later.

Set goals for yourself (did I understand the FI correctly?):

• Solve problems 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 it - to streamline new knowledge. It is difficult to say whether this article can help someone in the future, or rather, someone will help me by pointing out errors or suggesting improvements.

Summation and Filtering

The very beginning - downloading rock and googling in search of "how to run Main" I will skip. Handled - and all right.

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

Google helped me find examples of band 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: I use a ready-made range setting - and a ready-made sum function. I vaguely remembered the aggregating functions and rewrote the sum in twenty minutes using reduce (remembered it from Python). 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 do it 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 will not do this further - we believe that if I know how to write some kind of library function, then I can use it.

UPD
After a hint in the comments I realized that I can use 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 turned out to be easy. For example, I chose one of the old problems - triangular numbers . It is necessary to answer whether the entered number is triangular or not. In an ugly way, I created a list of triangular numbers and then checked whether it was entered in it - but I mastered the map function (which I know mostly 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") } 

Without branches at all, it doesn’t work out yet - I reassure myself that they are small.

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

I got a more general task - you 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 to have five more similar tasks - count in a cycle, transform, output - until I was bored.

Stream-s and iterations "before lunch"

I remember Collatz's hypothesis from some children's book - then I spent almost a day checking it on a piece of paper for the number 97 (did not succeed). Having found the appropriate task, I thought that I would pull it out quickly, but in fact I only mastered the next day.

First I wrote with a recursive function (it seems like I did it above), but then I began to look for some more ready approach. Thanks to this, I met Stream, iterate and takeWhile.

So, the numbers in the line are given - you need to calculate how many iterations the Collatz transformation for each of them will lead to one:

 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 ran into a real disaster.

Simple Numbers

Prime numbers I (mostly with the help of monotonous exercises with ProjectEuler from the time of learning Java) used to generate with the help of trial division. Suddenly it turned out that in a functional form it is (at least for me) to write very difficult. After all, in the cycle you need to check all the new and new numbers, adding them to the resulting array, which at the same time goes this check ...

Here's the task - for given indices, output simple numbers with corresponding sequence numbers. I thought it was worth only generating an array - and hurray ...

Having spent half a day, I already took to browse the Internet in search of clues. Unfortunately, the frills like this “one-liner” not only did not bring me closer to the solution, but also strengthened the feeling of my own inferiority.

In the end, I won by inventing a recurrent function, where the list of already found numbers and the next number to be checked are transferred. Here is the 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 one hundred — their performance obviously suffered due to implicit internal iterations ...

I do not like what happened. I found some apparently scientific article on the generation of prime numbers in a functional style, where, it seems, it is hinted that it is preferable for the OP to try the Eratosthenes sieve approach. However, I still feel weak enough in Scala to figure out how to fill a sieve immutable. Although now - right while writing this text - it came up with the idea that you need to use something like an immutable HashSet.

I hope that by the time I am ripe to write about the continuation of my experiments (if this is relevant) I will have the best solution.

Conclusion

At this point I dare to thank you for reading about my misadventures. I wrote about them first of all because those few tutorials on php I faced for some reason diligently showed me examples that are easy to write in a functional style - and avoided those from which the brain swells.

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