5

I am learning functional programming using scala. In general I notice that for loops are not much used in functional programs instead they use map.

Questions

  1. What are the advantages of using map over for loop in terms of performance, readablity etc ?

  2. What is the intention of bringing in a map function when it can be achieved using loop ?

Program 1: Using For loop

val num = 1 to 1000
val another = 1000 to 2000
for ( i <- num )
{
  for ( j <- another) 
  {
    println(i,j)
  }
}

Program 2 : Using map

val num = 1 to 1000
val another = 1000 to 2000
val mapper = num.map(x => another.map(y => (x,y))).flatten
mapper.map(x=>println(x))

Both program 1 and program 2 does the same thing.

Knight71
  • 2,927
  • 5
  • 37
  • 63
  • For the example you give (print output), you would not use map but you would use iter. Map is what you use when you transform a collection element wise from type A to type B. – BitTickler May 23 '15 at 20:14
  • Note that `for` loops in Scala are converted by the compiler into operations including `map` and `flatMap` - see [this question](http://docs.scala-lang.org/tutorials/FAQ/yield.html), for example – DNA May 23 '15 at 20:20
  • @DNA So for loop is just a syntatic sugar which will be converted to map and flatMap by compiler. – Knight71 May 23 '15 at 20:27
  • Syntactic salt, more. A homage to those struggling to transition, I would say. – BitTickler May 23 '15 at 20:28

4 Answers4

4

The answer is quite simple actually.

Whenever you use a loop over a collection it has a semantic purpose. Either you want to iterate the items of the collection and print them. Or you want to transform the type of the elements to another type (map). Or you want to change the cardinality, such as computing the sum of the elements of a collection (fold).

Of course, all that can also be done using for - loops but to the reader of the code, it is more work to figure out which semantic purpose the loop has, compared to a well known named operation such as map, iter, fold, filter, ...

Another aspect is, that for loops lead to the dark side of using mutable state. How would you sum the elements of a collection in a for loop without mutable state? You would not. Instead you would need to write a recursive function. So, for good measure, it is best to drop the habit of thinking in for loops early and enjoy the brave new functional way of doing things.

BitTickler
  • 10,905
  • 5
  • 32
  • 53
  • This means that for loop is avoided because that makes the programmer to think of a recursive function to solve problems. – Knight71 May 23 '15 at 20:28
  • It took me a few months to get used to it. But once you have you new "bag of tricks" ready, you do not really miss loops and the thought "I need a loop" leads to your fingers typing something recursive. But as I am not a scala programmer, a word of warning. I am not sure Scala supports tail recursion. I am not sure of the opposite, either, though. – BitTickler May 23 '15 at 20:31
  • 2
    Scala does have some tail recursion support - see [this question](https://stackoverflow.com/questions/3114142/what-is-the-scala-annotation-to-ensure-a-tail-recursive-function-is-optimized) – DNA May 23 '15 at 20:33
3

I'll start by quoting Programming in Scala. "Every for expression can be expressed in terms of the three higher-order functions map, flatMap and filter. This section describes the translation scheme, which is also used by the Scala compiler." http://www.artima.com/pins1ed/for-expressions-revisited.html#23.4

So the reason that you noticed for-loops are not used as much is because they technically aren't needed, and any for expressions you do see are just syntactic sugar which the compiler will translate into some equivalent. The rules for translating a for expression into a map/flatMap/filter expression are listed in the link above.

Generally speaking, in functional programming there is no index variable to mutate. This means one typically makes heavy use of function calls (often in the form of recursion) such as list folds in place of a while or for loop.

For a good example of using list folds in place of while/for loops, I recommend "Explain List Folds to Yourself" by Tony Morris. https://vimeo.com/64673035

If a function is tail-recursive (denoted with @tailrec) then it can be optimized so as to not incur the high use of the stack which is common in recursive functions. In this case the compiler can translate the tail-recursive function to the "while loop equivalent".

To answer the second part of Question 1, there are some cases where one could make an argument that a for expression is clearer (although certainly there are cases where the opposite is true too.) One such example is given in the Coursera.org course "Functional Programming with Scala" by Dr. Martin Odersky:

for {
  i <- 1 until n
  j <- 1 until i
  if isPrime(i + j)
} yield (i, j)

is arguably more clear than

(1 until n).flatMap(i =>
  (1 until i).withFilter(j => isPrime(i + j))
    .map(j => (i, j)))

For more information check out Dr. Martin Odersky's "Functional Programming with Scala" course on Coursera.org. Lecture 6.5 "Translation of For" in particular discusses this in more detail.

Also, as a quick side note, in your example you use

mapper.map(x => println(x))

It is generally more accepted to use foreach in this case because you have the intent of side-effecting. Also, there is short hand

mapper.foreach(println)

As for Question 2, it is better to use the map function in place of loops (especially when there is mutation in the loop) because map is a function and it can be composed. Also, once one is acquainted and used to using map, it is very easy to reason about.

scenefinale
  • 33
  • 3
1

The two programs that you have provided are not the same, even if the output might suggest that they are. It is true that for comprehensions are de-sugared by the compiler, but the first program you have is actually equivalent to:

val num = 1 to 1000
val another = 1000 to 2000
num.foreach(i => another.foreach(j => println(i,j)))

It should be noted that the resultant type for the above (and your example program) is Unit

In the case of your second program, the resultant type of the program is, as determined by the compiler, Seq[Unit] - which is now a Seq that has the length of the product of the loop members. As a result, you should always use foreach to indicate an effect that results in a Unit result.

gpampara
  • 11,989
  • 3
  • 27
  • 26
0

Think about what is happening at the machine-language level. Loops are still fundamental. Functional programming abstracts the loop that is implemented in conventional programming.

Essentially, instead of writing a loop as you would in conventional or imparitive programming, the use of chaining or pipelining in functional programming allows the compiler to optimize the code for the user, and map is simply mapping the function to each element as a list or collection is iterated through. Functional programming, is more convenient, and abstracts the mundane implementation of "for" loops etc. There are limitations to this convenience, particularly if you intend to use functional programming to implement parallel processing.

It is arguable depending on the Software Engineer or developer, that the compiler will be more efficient and know ahead of time the situation it is implemented in. IMHO, mid-level Software Engineers who are familiar with functional programming, well versed in conventional programming, and knowledgeable in parallel processing, will implement both conventional and functional.

Runnermann
  • 1
  • 1