3

I'm trying to write a functional approach in scala to get a list of all numbers between 1 & 1000 that are divisible by 3 or 5

Here is what I have so far :

  def getListOfElements(): List[Int] = { 
  val list = List()

    for (i <- 0 until 1000) {
        //list.
  } 
  list match {
    case Nil => 0
  } 
  list
}  

The for loop seems like an imperative approach and I'm not sure what to match on in the case class. Some guidance please ?

2

6 Answers 6

7

Here's how I would do it with a for expression.

for( i <- 1 to 1000 if i % 3 == 0 || i % 5 == 0) yield i

This gives:

 scala.collection.immutable.IndexedSeq[Int] = Vector(3, 5, 6, 9, 10, 12, 15, 18, 20, 21...

Here's another approach filtering on a Range of numbers.

scala> 1 to 1000
res0: scala.collection.immutable.Range.Inclusive = Range(1, 2, 3, 4, 5, 6, 7, 8, 9, 10...


scala> res0.filter(x => x % 3 == 0 || x % 5 == 0)
res1: scala.collection.immutable.IndexedSeq[Int] = Vector(3, 5, 6, 9, 10, 12, 15, 18, 20, 21...

If you really want a List on the return value use toList. e.g. res0.toList.

1
  • 1
    filter is not another approach to for+if, it is exactly the same. And don't use x toList. That is a postfix operator, which is error prone and therefore hided behind a flag in 2.10.
    – kiritsuku
    Dec 12, 2012 at 18:21
3

another aproach:

(1 to 1000).filter(i => i % 3 == 0 || i % 5 == 0)
3
(Range(3, 1000, 3) ++ Range(5, 1000, 5)).toSet.toList.sorted

Sorted can be omitted.

2

Looks like Brian beat me to it :)

Just thought I'd mention that a Stream might be more preferable here for better performance:

val x = (1 until 1000).toStream           //> x  : scala.collection.immutable.Stream[Int] = Stream(1, ?)
x filter (t=>(t%3==0)||(t%5==0))          //> res0: scala.collection.immutable.Stream[Int] = Stream(3, ?)
2
  • 1
    toStream is an overkill ;) it is just 1000 elements.
    – Jakozaur
    Dec 12, 2012 at 17:41
  • 1
    Well, no harm I guess. Makes it instantly scalable if you're using much larger ranges :) Dec 12, 2012 at 17:59
2

The problem from projecteuler.net also wants a sum of those numbers at the end.

"Find the sum of all the multiples of 3 or 5 below 1000."

object prb1 {
  def main(args: Array[String]) {
    val retval = for{ a <- 1 to 999
                      if a % 3 == 0 || a % 5 == 0
    } yield a
    val sum = retval.reduceLeft[Int](_+_)
    println("The sum of all multiples of 3 and 5 below 1000 is " + sum)
  }
}

The correct answer should be 233168

1
  • What exactly is your question? Dec 22, 2014 at 23:51
0

No any answer without division or list recreation. No any answer with recursion.

Also, any benchmarking?

@scala.annotation.tailrec def div3or5(list: Range, result: List[Int]): List[Int] = {
  var acc = result
  var tailList = list
  try {
    acc = list.drop(2).head :: acc   // drop 1 2 save 3
    acc = list.drop(4).head :: acc   // drop 3 4 save 5
    acc = list.drop(5).head :: acc   // drop 5 save 6 
    acc = list.drop(8).head :: acc   // drop 6 7 8 save 9
    acc = list.drop(9).head :: acc   // drop 9 save 10
    acc = list.drop(11).head :: acc  // drop 10 11 save 12
    acc = list.drop(14).head :: acc  // drop 12 13 14 save 15 
    tailList = list.drop(15)         // drop 15             
  } catch {
    case e: NoSuchElementException => return acc // found
  }
  div3or5(tailList, acc) // continue search  
}

div3or5(Range(1, 1001), Nil)

EDIT

scala> val t0 = System.nanoTime; div3or5(Range(1, 10000001), Nil).toList; 
(System.nanoTime - t0) / 1000000000.0
t0: Long = 1355346955285989000
res20: Double = 6.218004

One of answers that looks good to me:

scala> val t0 = System.nanoTime; Range(1, 10000001).filter(i => 
i % 3 == 0 || i % 5 == 0).toList; (System.nanoTime - t0) / 1000000000.0
java.lang.OutOfMemoryError: Java heap space

Another one:

scala> val t0 = System.nanoTime; (Range(1, 10000001).toStream filter (
(t: Int)=>(t%3==0)||(t%5==0))).toList ; (System.nanoTime - t0) / 1000000000.0
java.lang.OutOfMemoryError: Java heap space

First one:

scala> val t0 = System.nanoTime; (for( i <- 1 to 10000000 if i % 3 == 0 || 
i % 5 == 0) yield i).toList; (System.nanoTime - t0) / 1000000000.0
java.lang.OutOfMemoryError: Java heap space

Why Scala does not optimize for example Vector -> List?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.