A basic linked list implementation in scala

LinkedListQ.sc

// We are going to create our own implementation of a singly linked list,
// a recursive data structure often used in scala

// Define the type of data structure
sealed trait List[+A]

// Define the empty list (Nil)
case object Nil extends List[Nothing]

// Define the node containing a value (Cons)
case class Cons[+A](head: A, tail: List[A]) extends List[A]

// Define an empty list:
val emptyList = Nil

// Define a list containing one value:
val nonEmptyList = Cons("lol", Nil)

// Define a list containing 5 Ints
val fiveInts: List[Int] = Cons(3, Cons(5, Cons(33, Cons(-22, Cons(1000, Nil)))))

// Now we can define lists. We still need to define some operations for our structure.
// The time has come to look at pattern matching, a very useful construct in scala.
// We will be using

// Pattern matching... (p 33)
// Take a look at the docs:
// http://docs.scala-lang.org/tutorials/tour/pattern-matching.html

// Pattern matching allows us control the program flow based on the types/values of your data.
// Pattern matching starts from the top, and keeps looking until a match is found. If a match is found,
// the rest of the patterns are not considered.
// If no match is found, an error is thrown, so be sure to match all possible cases.
// An underscore catchall can be useful for avoiding this.

// This is the underscore catchall.
val alwaysFortyTwo = fiveInts match {
  case _ => 42
}

// Here we use x to refer to the head of the cons, and underscore to refer to the tail.
// We use x because we want to refer to the head later in the statement.
// The underscore is used here since we don't really care about the tail here,
// but we still need it to correctly express the cons data structure.
val twelveTimesHead = fiveInts match {
  case Cons(x, _) => x*12
  case Nil => // If fiveInts was Nil, we would need to handle that case here
}

// Get the first element out of your list
val firstValue = fiveInts match {
  case Cons(x, _) => x
  case _ => // This is a catchall, and another way of handling Nil cases.
            // In this case we would probably want to throw an error,
            // since we are trying to access an undefined first value.
}

// Get the tail of your list
val listTail = fiveInts match {
  case Cons(_, y) => y
}

// Test your understanding:
// What will this pattern match result in?
/*
val dumbList: List[Int] = Cons(1, Cons(2, Cons(3, Nil)))

dumbList match {
  case Cons(x, Cons(2, Cons(4, _))) => x
  case Nil => 42
  case Cons(x, Cons(y, Cons(3, Cons(4, _)))) => x + y
  case Cons(h, t) => h + sum(t)
  case _ => 101
}
*/

// Define a sum operation for Ints in a companion object

object List {

  def sum(numbers: List[Int]): Int = numbers match {
    case Nil => 0
    case Cons(value, tail) => value + sum(tail)
  }

  def product(numbers: List[Int]): Int = numbers match {
    case Cons(0, _) => 0
    case Nil => 1
    case Cons(value, tail) => value * product(tail)
  }

  def prepend(numbers: List[Int], newHead: Int): List[Int] = Cons(newHead, numbers)

  def takeOddNumbers(numbers: List[Int]): List[Int] = {

    def impl(acc: List[Int], remainingNumbers: List[Int]): List[Int] = remainingNumbers match {
      case Nil => acc
      case Cons(head, tail) =>
        if (head % 2 == 1)
          impl(List.prepend(acc, head), tail)
        else
          impl(acc, tail)
    }

    impl(Nil, numbers)
  }

  def filter(numbers: List[Int], keepIf: Int => Boolean): List[Int] = {

    def impl(acc: List[Int], remainingNumbers: List[Int]): List[Int] = remainingNumbers match {
      case Nil => acc
      case Cons(head, tail) =>
        if ( keepIf(head) )
          impl(List.prepend(acc, head), tail)
        else
          impl(acc, tail)
    }

    impl(Nil, numbers)
  }

}

// Test your sum function with your list containing 5 ints
List.sum(fiveInts)

// Define a product operation for Ints
List.product(fiveInts)

// Define a function that returns the list with one additional number added to the front
List.prepend(fiveInts, 44)

// Define a function that returns a list with all the even numbers removed
List.takeOddNumbers(fiveInts)

// Define a filter function that takes a list of numbers and a predicate function
// Use it to filter the even numbers out of your list
List.filter(fiveInts, x => x % 2 == 1)