Scala Problem Number Four

Lets solve now the problem number four, from the Scala 99 Problems. This one goes as follows:

P04 (*) Find the number of elements of a list.
Example:

scala> length(List(1, 1, 2, 3, 5, 8))
res0: Int = 6

Lets start with the ridiculously easy way: using the API:

  def length(list: List) = {
    list.size
  }

Now lets try a different approach, with pattern matching and recursion:

  def count(acc: Int, remaining: List[Any]): Int = remaining match {
    case Nil => acc
    case x :: tail => count(acc + 1, tail)
  }

  def length(list: List[Any]) = count(0, list)

The function count receives an accumulator and a list. If the list is empty, it simply returns the accumulator. Otherwise, it calls itself again, passing an augmented accumulator and the tail of the list. This means that the recursion goes on until the list has nothing more inside it. We are removing the list elements, one by one, and counting them.

One last possibility, before linking the original solution:

  def length(list: List[Any]) = {
    list.foldLeft(0) { (count, item) => count + 1 }
  }

Here we are using foldLeft to process each element of the list and count the elements. Usually, we would use the list items to do some calculation to be used in the final value returned by foldLeft, but since all we want is to count the list elements, we are ignoring the item and just increasing the count. Pretty simple.

If you want to take a look at the original solution for this problem, click here. Looking at this solution, it looks like I was using tail recursion above and didn’t notice. Also, its foldLeft version is more compact (but less didactic, I guess…). Finally, I didn’t consider the direct recursion possibility – probably because I was having fun trying to figure out the tail recursion version =)

Advertisements
This entry was posted in scala and tagged , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s