Answer of Scala exercises for beginners

gistfile1.scala

// You are not permitted to use these List methods:
// * length
// * map
// * filter
// * ::: (and variations such as ++)
// * flatten
// * flatMap
// * reverse (and variations i.e. reverseMap, reverse_:::)
// This also means you are not permitted to use for-comprehensions on Lists.
// You are permitted to use the functions you write yourself. For example, Exercise 2 may use Exercise 1 or Exercise 3.
// Using permitted existing methods where appropriate will attract marks for elegance.

// TOTAL marks:    /66

object Exercises {
  def succ(n: Int) = n + 1
  def pred(n: Int) = n - 1

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

  def foldRight[A, B](x: List[A], f: (A, B) => B, v: B): B = x match {
    case Nil => v
    case a:: tail => f(a, foldRight(tail, f, v))
  }
  def foldLeft[A, B](x: List[A], f: (B, A) => B, v: B): B = x match {
    case Nil => v
    case a :: tail => foldLeft(tail, f, f(v, a))
  }

  def foldLeft2[A, B](x: List[A], f: (B, A) => B, v: B): B = {
    def h(a:A, g:B => B): B => B = (b:B) => g(f(b, a))
    foldRight(x, h, id[B] _)(v)
  }

  // Exercise 1
  // Relative Difficulty: 1
  // Correctness: 2.0 marks
  // Performance: 0.5 mark
  // Elegance: 0.5 marks
  // Total: 3
  def add(x: Int, y: Int): Int = y match {
    case 0 => x
    case _ => add(succ(x), pred(y))
  }

  // Exercise 2
  // Relative Difficulty: 2
  // Correctness: 2.5 marks
  // Performance: 1 mark
  // Elegance: 0.5 marks
  // Total: 4
  def sum(x: List[Int]): Int = x match {
    case Nil => 0
    case a :: tail => add(a, sum(tail))
  }
  def sum2(x: List[Int]): Int = {
    def f(x: List[Int], r: Int): Int = x match {
      case Nil => r
      case a :: tail => f(tail, add(r, a))
    }
    return f(x, 0)
  }
  def sum3(x: List[Int]): Int = foldRight(x, add, 0)

  // Exercise 3
  // Relative Difficulty: 2
  // Correctness: 2.5 marks
  // Performance: 1 mark
  // Elegance: 0.5 marks
  // Total: 4
  def length[A](x: List[A]): Int = x match {
    case Nil => 0
    case a :: tail => 1 + length(tail)
  }
  def length2[A](x: List[A]): Int = sum(map(x, (_:A) => 1))
  def length3[A](x: List[A]): Int = foldRight(x, (a:A, b:Int) => 1 + b, 0)

  // Exercise 4
  // Relative Difficulty: 5
  // Correctness: 4.5 marks
  // Performance: 1.0 mark
  // Elegance: 1.5 marks
  // Total: 7
  def map[A, B](x: List[A], f: A => B): List[B] = x match {
    case Nil => Nil
    case a :: tail => f(a) :: map(tail, f)
  }
  def map2[A, B](x: List[A], f: A => B): List[B] = foldRight(x, (a:A, l:List[B]) => f(a) :: l, Nil)

  // Exercise 5
  // Relative Difficulty: 5
  // Correctness: 4.5 marks
  // Performance: 1.5 marks
  // Elegance: 1 mark
  // Total: 7
  def filter[A](x: List[A], f: A => Boolean): List[A] = x match {
    case Nil => Nil
    case a :: tail if f(a) => a :: filter(tail, f)
    case a :: tail         => filter(tail, f)
  }
  def filter2[A](x: List[A], f: A => Boolean): List[A] = foldRight(x, (a:A, l:List[A])=> if (f(a)) a :: l else l, Nil)

  // Exercise 6
  // Relative Difficulty: 5
  // Correctness: 4.5 marks
  // Performance: 1.5 marks
  // Elegance: 1 mark
  // Total: 7
  def append[A](x: List[A], y: List[A]): List[A] = x match {
    case Nil => y
    case a :: tail => a :: append(tail, y)
  }
  def append2[A](x: List[A], y: List[A]): List[A] = foldRight(x, (a:A, l:List[A]) => a :: l, y)

  // Exercise 7
  // Relative Difficulty: 5
  // Correctness: 4.5 marks
  // Performance: 1.5 marks
  // Elegance: 1 mark
  // Total: 7
  def concat[A](x: List[List[A]]): List[A] = x match {
    case Nil => Nil
    case a :: tail => append(a, concat(tail))
  }
  def concat2[A](x: List[List[A]]): List[A] = foldRight(x, append[A], Nil)

  // Exercise 8
  // Relative Difficulty: 7
  // Correctness: 5.0 marks
  // Performance: 1.5 marks
  // Elegance: 1.5 mark
  // Total: 8
  def concatMap[A, B](x: List[A], f: A => List[B]): List[B] = x match {
    case Nil => Nil
    case a :: tail => append(f(a), concatMap(tail, f))
  }
  def concatMap2[A, B](x: List[A], f: A => List[B]): List[B] = foldRight(x, (a:A, l:List[B]) => append(f(a), l), Nil)

  // Exercise 9
  // Relative Difficulty: 8
  // Correctness: 3.5 marks
  // Performance: 3.0 marks
  // Elegance: 2.5 marks
  // Total: 9
  def maximum(x: List[Int]): Int = x match {
    case Nil => 0
    case a :: tail => max(a, maximum(tail))
  }
  def max(a: Int, b:Int): Int = if (a > b) a else b
  def maximum2(x: List[Int]): Int = foldRight(x, max, 0)

  // Exercise 10
  // Relative Difficulty: 10
  // Correctness: 5.0 marks
  // Performance: 2.5 marks
  // Elegance: 2.5 marks
  // Total: 10
  def reverse[A](x: List[A]): List[A] = {
    def rev[A](y: List[A], r:List[A]): List[A] = y match {
      case Nil => r
      case a :: tail => rev(tail, a :: r)
    }
    rev(x, Nil)
  }
  def reverse2[A](x: List[A]): List[A] = foldLeft2(x, (l:List[A], a:A) => a :: l, Nil)

}