List of functions mapped on view - is the view traversed more than once?

Question

I'm trying to wrap my head around how views are used in Scala. I have the following example code:

class Square extends (Seq[Int] => Int) {
    def apply(x: Seq[Int]) = x.reduce(_ * _)
}

class Sum extends (Seq[Int] => Int) {
    def apply(x: Seq[Int]) = x.reduce(_ + _)
}

val functionList = List(new Square, new Sum)

val list = List(1, 2, 3, 4, 5, 6)
val view = list.view

functionList.map(f => f(view))

My questions are:

Will the list be traversed once or twice in the above example when the map is applied?
If it is traversed more than once, is there any other design pattern that I can use that allows me to define a collection of functions and map over some other collection while only traversing the second collection once?

score 1 · Accepted Answer · edited May 23 '17 at 11:56

The list is being traversed twice. What you're essentially doing is first taking the Square function and applying a reduce on all the elements. Next the Sum function will also apply a reduce on all the elements.

A view turns the collection into a lazy one. Meaning if you have multiple transformations they will only be applied when they are needed. In this case, I don't think this has any impact on your solution, since you're applying functions that do calculations on whole collections (meaning they need to be evaluated to get the result). See this question for an answer on when to use views.

Traversing the second collection once isn't easy in this case. You have two functions that do a reduce on the whole list, meaning each one needs a seperate accumulator and has a seperate result. If you want to only traverse your element list once, you need to change your logic a bit. Instead of defining operations on the whole list, you need to define operations on how to combine two elements. Here's what I came up with:

val functionListWithInitialValues = List(
  ((a: Int, b: Int) => a * b, 1), //This is a Tuple that defines how to combine two calculations and what the initial value is.
  ((a: Int, b: Int) => a + b, 0)
)

val results = list.foldLeft(functionListWithInitialValues) {
  case (accumulators, next) => // foldLeft gives us the previous results
                               // (which is essentailly a Tuple(function, value)),
                               // and the next element, to combine with the previous result.
    // Now let's go through our functions and apply the functions on the accumulator and the next element
    accumulators.map {
      case (function, previousResult) =>
        (function, function(previousResult, next))
    }
}
results.map { case (function, result) => println(result) }

This solution will only traverse your elements once, applying the combining function on the accumulator and the next element.

score 0 · Answer 2 · answered Nov 15 '13 at 13:16

Not sure what List you are talking about.

You are applying the map on an actual strict List so functionList will be traversed once, and applying 'f' to the view will reduce the List[Int] for each function in functionList.

If you want to apply your modificators lazily then functionList should be a view so that 'map' is not strict.

List of functions mapped on view - is the view traversed more than once?

2 Answers2