CODEWITHSUNDEEP
algorithmscalacollectionsidioms
Garrett Rowe
Garrett Rowe

Reputation: 1235

Idiomatic Scala solution to imperative code

What are some ideas for expressing this function in 'idiomatic' Scala. Or more precisely, is there a way to remove the local vars without sacrificing readability?

def solve(threshold: Int)(f: Int => Int): Int = {
  var sum = 0
  var curr = 0
  while(sum < threshold) {
   sum += f(curr)
   curr += 1
  }
  curr
}

The only thing I could come up with was this, but it's longer and less readable in my opinion.

def solve2(threshold: Int)(f: Int => Int): Int = {
  val resultIterator = Iterator.iterate (0, 0) { case (curr, sum) =>
    (curr + 1, sum + f(curr))
  }
  (resultIterator find (_._2 >= threshold)).get._1
}

Upvotes: 9

Views: 450

Answers (5)

Dan Burton
Dan Burton

Reputation: 53705

Here is how I would do it in Haskell: 

solve threshold f = snd $ until test step (0, 0)
  where test (sum, i) = sum >= threshold
        step (sum, i) = (sum + f i, succ i)

This clearly marks the test, the step, and the initial values, just like the imperative version. I am not sure if scala has until in the libs somewhere, but it is trivial to define:

def until[A](test: A => Boolean)(f: A => A)(v: A): A = {
  if (test(v)) {
    v
  } else {
    until(test)(f)(f(v))
  }
}

def solve(threshold: Int)(f: Int => Int): Int = {
  def test = (sum: Int, i: Int) => sum >= threshold
  def step = (sum: Int, i: Int) => (sum + f(i), i + 1)
  until(test.tupled)(step.tupled)((0, 0))._2
}

Upvotes: 4

AndreasScheinert
AndreasScheinert

Reputation: 1918

I always wonder when people talk about 'idiomatic' scala. Because in my opinion everyone has his own perception of idiomatic. If you are looking for a functional solution I would like to suggest you to take a look at the 'essence of the iterator pattern' . There is actually a very good blogpost in scala about this check it out here : http://etorreborre.blogspot.com/2011/06/essence-of-iterator-pattern.html

Upvotes: 1

Rex Kerr
Rex Kerr

Reputation: 167901

You could

def solve(threshold: Int, i: Int = 0)(f: Int => Int) = {
  if (threshold <= 0) i else solve(threshold - f(i), i+1)(f)
}

but I'm not sure that's actually clearer. Note that it's actually more characters than a compact version of the while loop:

def solve(threshold: Int)(f: Int => Int) = {
  var s,i = 0; while (s < threshold) { s += f(i); i += 1 }; i
}

Loops with mutable variables aren't always bad, "idiomatic" or no. Just keep the mutable state safely contained within the function, and all anyone else sees is a stateless function to call.

Incidentally, although sum is a sensible variable name, curr is questionable. What's wrong with i? It's widely used as an index variable, and anyway, having a variable at all is a nuisance; the point is you take something and increment it, whatever it is, by one step each time, and then return it. It is this flow of logic, not the name, which tells you (and others) what it is for.

Upvotes: 7

missingfaktor
missingfaktor

Reputation: 92066

def solve(threshold: Int)(f: Int => Int): Int = {
  Iterator.from(0).map(f).scanLeft(0)(_ + _).indexWhere(threshold <=)
}

In my opinion, the loop version is much clearer.

Upvotes: 13

Dan Simon
Dan Simon

Reputation: 13137

The most direct approach is to turn the while loop into a nested tail-recursive function.

def solve(threshold: Int)(f: Int => Int): Int = {
    def solveLoop(sum: Int, curr: Int): Int = if (sum < threshold) {
        solveLoop(sum + f(curr), curr + 1)
    } else {
        curr
    }
    solveLoop(0,0)
}

This is the standard "functional" way of looping.

Upvotes: 10

Related Questions