1package org.onetofive
 2
 3import org.scalatest._
 4import OneToFive._
 5
 6class OneToFiveSuite extends FunSuite {
 7  val list = List(1, 2, 3, 4, 5)
 8
 9  test("1. get the last element of a list") {
10    assert(last_procedural(list) === 5)
11    assertThrows[NoSuchElementException] { last_procedural(Nil) }
12
13    assert(last_recursive(list) === 5)
14    assertThrows[NoSuchElementException] { last_recursive(Nil) }
15  }
16
17  test("2. get the second last element of a list") {
18    assert(penultimate_procedural(list) === 4)
19    assertThrows[NoSuchElementException] { penultimate_procedural(Nil) }
20
21    assert(penultimate_recursive(list) === 4)
22    assertThrows[NoSuchElementException] { penultimate_recursive(Nil) }
23
24    assert(take_last_nth_procedural(list, 3) === 3)
25    assertThrows[NoSuchElementException] { take_last_nth_procedural(Nil, 3) }
26    assertThrows[IllegalArgumentException] { take_last_nth_procedural(list, 0) }
27
28    assert(take_last_nth_recursive(list, 2) === 4)
29    assertThrows[NoSuchElementException] { take_last_nth_recursive(Nil, 2) }
30    assertThrows[IllegalArgumentException] { take_last_nth_recursive(list, 0) }
31  }
32
33  test("3. Find the Kth element of a list") {
34    assert(nth_procedural(list, 2) === 2)
35    assertThrows[NoSuchElementException] { nth_procedural(Nil, 2) }
36
37    assert(nth_recursive(list, 2) === 2)
38    assertThrows[NoSuchElementException] { nth_recursive(Nil, 2) }
39  }
40
41  test("4. Find the number of elements of a list") {
42    assert(count_recursive(Nil) === 0)
43    assert(count_with_fold(Nil) === 0)
44
45    assert(count_recursive(list) === list.length)
46    assert(count_with_fold(list) === list.length)
47  }
48
49  test("5. Reverse a list") {
50    val reversed = list.reverse
51
52    assert(reverse(list) === reversed)
53    assert(reverse_recursive(list) === reversed)
54    assert(reverse_tailrecursive(list) === reversed)
55    assert(reverse_withfold(list) === reversed)
56  }
57}

  1package org.onetofive
  2
  3import scala.annotation.tailrec
  4
  5object OneToFive extends App {
  6  def last_procedural[A](xs: List[A]): A = xs.last
  7
  8  def last_recursive[A](xs: List[A]): A = xs match {
  9    case x :: Nil => x
 10    case head :: tail => last_recursive(tail)
 11    case _ => throw new NoSuchElementException
 12  }
 13
 14  def penultimate_procedural[A](xs: List[A]): A = if(xs.isEmpty) throw new NoSuchElementException else xs.init.last
 15
 16  def penultimate_recursive[A](xs: List[A]): A = xs match {
 17    case head :: List(x) => head
 18    case head :: tail => penultimate_recursive(tail)
 19    case _ => throw new NoSuchElementException
 20  }
 21
 22  def take_last_nth_procedural[A](xs: List[A], n: Int): A = {
 23    if(xs.isEmpty) throw new NoSuchElementException
 24    if(n < 1) throw new IllegalArgumentException
 25
 26    xs.takeRight(n).head
 27  }
 28
 29  // first I thought that is smart to take the last element as looking to (length - index)
 30  // but then I realized that Lists doesn't have a normal length property, it is calculated
 31  // again and again recursively through traversing the whole List. So just a small optimization:
 32  def take_last_nth_recursive[A](xs: List[A], n: Int): A = {
 33    val l = xs.length
 34
 35    def iter[A](ys: List[A], n: Int): A = ys match {
 36      case _ if(n < 1) => throw new IllegalArgumentException
 37      case _ :: tail if(l - n != 0) => take_last_nth_recursive(tail, n)
 38      case head :: _ if(l - n == 0) => head
 39      case _ => throw new NoSuchElementException
 40    }
 41
 42    iter(xs, n)
 43  }
 44
 45  // even better
 46  def nth_procedural[A](xs: List[A], n: Int): A = xs.takeRight(xs.length - n + 1).head
 47
 48  def nth_recursive[A](xs: List[A], n: Int): A = xs match {
 49    case _ if(n < 1) => throw new IllegalArgumentException
 50    case _ if(xs.length == 0) => throw new NoSuchElementException
 51    case head :: _ if(n == 1) => head
 52    case _ :: tail => nth_recursive(tail, n - 1)
 53  }
 54
 55  // oh yay! tail recursive
 56  def count_recursive[A](xs: List[A]): Int = {
 57    @tailrec
 58    def iter(ys: List[A], n: Int): Int = ys match {
 59      case Nil => n
 60      case _ :: tail => iter(tail, n + 1)
 61    }
 62
 63    iter(xs, 0)
 64  }
 65
 66  // even better
 67  def count_with_fold[A](xs: List[A]): Int = xs.foldLeft(0){ (acc, _) => acc + 1 }
 68
 69  // the obvious
 70  def reverse[A](xs: List[A]): List[A] = xs.reverse
 71
 72  // not tail recursive
 73  def reverse_recursive[A](xs: List[A]): List[A] = xs match {
 74    case Nil => Nil
 75    case head :: tail => reverse_recursive(tail) ::: List(head)
 76  }
 77
 78  // better
 79  def reverse_tailrecursive[A](xs: List[A]): List[A] = {
 80    @tailrec
 81    def iter(acc: List[A], ys: List[A]): List[A] = ys match {
 82      case Nil => acc
 83      case head :: tail => iter(head :: acc, tail)
 84    }
 85
 86    iter(Nil, xs)
 87  }
 88  // even better
 89  def reverse_withfold[A](xs: List[A]): List[A] = xs.foldLeft(Nil: List[A]){ (ys, x) => x :: ys }
 90
 91  /*
 92   WHAT I LEARNED?
 93
 94   * You can check thrown exceptions in your tests with assertThrows
 95   * you could add a @tailrec annotation so that you can be sure that your function is optimized by compiler as a tail recursive function.
 96   * in Lists nearly every function's complexity except head is linear. So better think twice when you want to write your own recursive functions
 97   * You can use fold or take functions for your recursive needs!
 98
 99  */
100}

1git clone https://github.com/dhalsim/scala-exercises.git
2cd scala-exercises
3sbt test