Problem 1 [Language]: Multiples of 3 and 5

[eloots]

How does the solution using Set, as demonstrated in one of the solutions, work ?

Answer:

Scala Sets work as mathematical sets. Every value of a set is unique within that set, i.e. there are no duplicates.

The Scala Set collection defines a number of useful operations that allow you to combine two sets.

For example, taking the union of two sets can be done using the ++ operator.

For example:

val set1 = Set(1,2,3)
val set2 = Set(3,4,5)

val setUnion = set1 ++ set2

println(setUnion)

will print the following:

Set(5, 1, 2, 3, 4)

As can be seen, Sets are unordered. Note that, in case you need an ordered Set, there is an implementation of such an animal in the Scala collection library.

As a bonus, there are other useful operators on Set such as & and &~ as demonstrated here:

scala> set1 & set2
res2: scala.collection.immutable.Set[Int] = Set(3)

scala> set1 &~ set2
res3: scala.collection.immutable.Set[Int] = Set(1, 2)

You should be able to figure out what these do for yourself. Quite powerful these Scala collections...

[samdebacker]

The advantage of going to a conference like Scala eXchange is that you learn new tricks. And so I stumbled over the withFilter method of the TraversableLike trait. Be warned, we are slipping into the M-word dungeons of Functional Programming. This might sound a bit scary for the newcomers, but really, there is nothing scary about it.
A trait in Scala is just like a Java 7 (and older) interface, but the methods defined in a trait can also have an implementation. A feature so powerful it got assimilated by Java 8 as default methods in an interface.
Remember the simple solution to this Euler problem is Scala looked like this:

(1 until 1000).filter(l => l % 3 == 0 || l % 5 == 0).sum

The filter method created from a collection a new collection. In this simple case this is not an issue, but imagine you start chaining filter, map and again filter methods you end up creating one collection after another. The withFilter method takes a different approach, in stead of constructing a new collection, it only registers the fact that a filter needs to be applied on the collection. It is only upon enumeration of the elements in the end result that the filter starts doing it's work. This resembles a bit the Stream approach if you have been following some of the previous posts. So the withFilter does not return a new collection but a FilterMonadic, another base trait of all Scala collection classes. Yes, Monads all the way down. The FilterMonadic is a very basic trait, only defining the bare map, flatMap, foreach and withFilter methods, so calculating the sum must be done with a foreach, as demonstrated in the withFilter solution:

var result = 0
(1 until 1000).withFilter(l => l % 3 == 0 || l % 5 == 0).foreach(result += _)
result

But not being happy with the very basic methods of FilterMonadic I stumbled on this Stackoverflow discussion with this little remark:

...you're not supposed to use withFilter yourself (apart from implicitly within for-expressions). Use view if you want maps / filters to be lazy.

The view method of TraversableLike returns a TraversableView that has all the nice methods of the collection library and and will behave in respect with the filter method a lot like the withFilter method. The solution with a view looks like this:

(1 until 1000).view.filter(l => l % 3 == 0 || l % 5 == 0).sum

[octonato]

In addition to Problem005, I also committed an over-engineered solution for Problem001.

The best and most straightforward solution is simply:

(1 until 1000).filter(l => l % 3 == 0 || l % 5 == 0).sum

But we can try to model our own Range object and explore some Scala features.
Once again there are separated commits.

P001: Range model
Defines a minimalistic Range model.

It has two methods, sum and toList. In both cases there is not intermediated collection. The range is defined with two Int as boundaries. The values between the beginning and the end of the range are only computed sum or toList are called. Note: no memoization here!

There is also a companion object that allow us to initialize a TotalRange.
(a TotalRange is a range that contains all elements from begin to end).

P001: controlling invariants on constructor
We add an assert to the constructor that asserts that the beginning is before or equals the end.
This is to illustrate how we can reinforce invariants.

P001: adding filtering
Adds the filtering method. With filtering we also introduce a FilteredRange which is a Range that does not contain all elements between begin and end.

At that point it must be obvious why we had initially a next(n:Int) and previous(n:Int). Methods sum and toList have a internal tailrec loop that calls next instead of simply incrementing the value.
Now that we had the filtering, we can use next/previous to calculate the next and previous value while applying the filter at the same time.

Calling withFilter on a FilteredRange produces another FilteredRange with a composed filter function. This is pretty much the example Luc explained. If I had done the same, I could have written:

  def withFilter(filter: (Int) => Boolean) : Range = {
    FilteredRange(this, filterFunc && filter) // must more elegant
  }

P001: foldLeft with Monoid
In the next commit we introduce the concept of Monoid. A monoid is very, very simple.

It's just a construct with two methods:

1. the first method defines an initial state for a given operation. We call it the zero function or method.
2. the second method allow you to reduce two values of same type to one single value, we'll call it append.

A Monoid trait looks like:

trait Monoid[T] {
  def zero:T
  def append(left:T, right:T)

An IntAddMonoid is Monoid for adding Ints.

object IntAddMonoid extends Monoid[Int] {
  def zero = 0
  def append(left:Int, right:Int) = left + right
}

and a ListIntMonoid that builds a List[Int]

object ListIntMonoid extends Monoid[List[Int]] {
  def zero = List[Int]() // zero is an empty list
  def append(left:List[Int], right:List[Int]) = left ++ right // merge two Lists
}

Now we move out the loop inner method from the sum and toList method to a foldLeft method.

def foldLeft[T](z: T)(op: (T, Int) => T) : T = {
    @tailrec
    def loop(num:Int, acc:T) : T = {
      if (num > end) acc
      else if (num == end) op(acc, num)
      else loop(next(num), op(acc, num))
    }
    loop(begin, z)
  }

Note: this implementation has the second parameter of the function op fixed to Int. The Range is not parameterized, so we always have a Int.

And now the definition of a foldLeft using a Monoid.

private def foldLeftMonoid[T](monoid:Monoid[T])(builder: (Int) => T) : T = {
    foldLeft(monoid.zero) { (acc, num) =>
      monoid.append(acc, builder(num))
    }
  }

Note the builder parameter on the second parameter block. It's a function from Int (the type of the Range) to T, the type of the Monoid. This may look silly in the case of sum, but it's NOT in the case of List.

Following we can see how to implement both sum and toList to use the foldLeftMonoid we just defined.

  def sum: Int = foldLeftMonoid(IntAddMonoid)(identity)
  def toList: List[Int] = foldLeftMonoid(ListIntMonoid) { n => List(n) }

Note: the sum method uses the identity function as builder. The identity function is defined in the Scala library (scala.Predef) and is always in scope.

The identity function is defined as:

def identity[A](x: A): A = x

For any given type A return the same value.

P005: adds from/to/until 'dsl' and problem solution

The last commit introduces a DSL to build ranges. It uses anonymous objects to create an intermediary object that will finally build a range.

object Range {
  def apply(start: Int, end: Int) : Range = TotalRange(start, end)

  def from(start:Int) = new  {
    def to(end:Int) : Range = TotalRange(start, end)
    def until(end:Int) : Range = TotalRange(start, end - 1)
  }
}

And you can use it as:

val range = Range.from(1).until(10)

This over-engineered solution has impressive performance! Compare it with the collection impl and the pure loop impl added on my Problem005 solution.
(add ironic laugh here)