Target audience: Beginner
Estimated reading time: 4'
Introduction
Contrary to C++ and Java, Scala does not allow developer to exit an iterative execution prematurely using a syntax equivalent to break.
var sum = 0 for( i <- 0 until 100) { sum += i if( sum > 400) break // won't compile! }
Scala purists tend to stay away from this type of constructs and use higher order collection methods such as
exists( p: (T) => Boolean)
find( p: (T) => Boolean)
takeWhile( p: (T) => Boolean
)
However these methods are not available outside collections. There are cases where a `break` construct may be a simpler solution.
This post review the different options to 'break' from a loop according to a predefined condition.
Breakable control
Although breaking out of a loop may not be appealing to "pure" functional developer, the Scala language provides formal Java and C++ developers with the option to use break and continue statements. The breakable statement define the scope for which break is valid.
import scala.util.control.Breaks._
var sum = 0
breakable {
for (i <- 0 until 100 ) {
sum += i
if( sum > 55)
break
}
}
Any experienced developer would be quite reluctant to use such an idiom: beside the fact that the accumulator is defined as a variable, the implementation is unnecessary convoluted adding a wrapper around the loop. Let's try to find a more functional like approach to breaking out of any loop.
scan & fold to the rescue
Luckily, Scala provides collections with functional traversal patterns that can be used and chained to break, elegantly from a loop. The following code snippets introduce applies some of those traversal patterns to an array and a associative map to illustrate the overall "functional" approach to iteration.
Let's consider the problem of extracting the elements of an array or map before a predefined condition is met for an element. For instance, let's extract the elements of an array or a hash map until one element has the value 0. The Scala programming language provide us with the takeWhile method (lines 7 & 10) that allows to to end traversing a collection and return a elements of the collection visited when a condition is met.
1
2
3
4
5
6
7
8
9
10
11 | val values = Array[Int](9, 45, 11, 0, 67, 33)
val mappedValues = Map[String, Int](
"A"->2, "B"->45, "C"->67, "D"->0, "E"->56
)
// Extract a subarray of values until the condition is met
values takeWhile( _ != 0) // -> Array(9, 45, 11)
// Extract a submap until the condition is met
mappedValues takeWhile( _._2 != 0)
// -> Map(E -> 56, A -> 2, B -> 45, C -> 67)
|
The second case consists in accumulating values until a condition on the accumulator is met. Contrary to fold and reduce methods which apply a function (i.e summation) to all the elements of a collection to return a single value, scan, scanLeft and scanRight methods return a collection of values processed by the function.
In the following example, the invocation of the higher order method scanLeft (lines 4 generates an array and a hash map with the cumulative values. The takeWhile method i(lines 5 & 8) s then applied to the resulting array or map to return a collection of cumulative values until the accumulator exceeds 56. The same invocation can be used to return the element which push the accumulator beyond the threshold.
1
2
3
4
5
6
7
8
9 | values.scanLeft(0)(_ + _).takeWhile (_ < 56)
//-> Array(0, 9, 54)
mappedValues.scanLeft(0) (_ + _._2)
.takeWhile( _ < 56)
val indexTargetEl = values.scanLeft(0)(_ + _)
.takeWhile (_ < 56).size -1
val targetEl = values(indexTargetEl)
|
Tail recursion
A third and elegant alternative to exit from a loop is using the tail recursion which is supported natively in the Scala language. The first method, findValue exits the loop when a condition on the value is reached (line 5). The second method, findCummulative, is implemented as a closure and exits when the sum of elements exceeds a predefined value (line 15).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | val values = Array[Int](9, 45, 11, 0, 67, 33)
@scala.annotation.tailrec
def findValue(values: Array[Int], index: Int) : Int = {
if( values(index) == 0 || index >= values.size)
index
else
findValue(values, index + 1)
}
val newValues = values.slice(0, findValue(values, 0))
val MAX_VALUE :Int = 86
@scala.annotation.tailrec
def findCumulative(sum: Int, index: Int): Int = {
if( index >= values.size ||sum >= MAX_VALUE)
index -1
else
findCumulative(sum + values(index), index + 1)
}
val newValues2 = values.slice(0, findCumulative(0, 0))
|
This concludes our review of three different Scala constructs available to developer to exit prematurely from a loop
- breakable construct
- Higher order method such as exists, find, takeWhile....
- tail recursion
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.