Functional List Utilities

In this assignment you will take your first steps in functional programming by writing a few functions that every beginning functional programmer writes. You’ll also gain some familiarity with Scala’s List class and polymorphic functions. Finally, you’ll see that you can implement any algorithm using only two constructs: if expressions and recursion.

The first 100 points of this assignment are relatively straightforward, but you may find the last four functions quite challenging. That’s fine. You’re developing an entirely new mental model of programming.

A language the doesn’t change the way you think about programming isn’t worth learning. – Paraphrased from Alan Perlis

Problem Description

You are a beginning functional programmer and you want to get a feel for its fundamental concepts and idioms.

Solution Description

Implement the following functions below following these rules:

def length[T](list: List[T]): Int

Return the number of elements in list.

Example:

scala> length(List(1,2,3))
res38: Int = 3

def find[T](item: T, list: List[T]): Int

Return the index of item in list, or -1 if item is not in list.

Example:

scala> find(0, List(1,2,3,4))
res0: Int = -1

scala> find(2, List(1,2,3,4))
res1: Int = 1

def reverse[T](list: List[T]): List[T]

Return a new List with the same elements as list, but in reverse order.

Hint: list.head returns a reference the the first element of a list. x::xs puts x at the front of a new list containing x and the elements of xs. So (x::xs).head == x.

Example:

scala> reverse(List(1,2,3,4))
res2: List[Int] = List(4, 3, 2, 1)

def map[T, U](fn: T => U, list: List[T]): List[U]

Return a new List which collects, in corresponding positions, the results of applying fn to each element in list.

Example:

scala> map((x: Int) => 2 * x, List(1,2,3,4))
res3: List[Int] = List(2, 4, 6, 8)

filter[T](fn: T => Boolean, list: List[T]): List[T]

Return a new List which contains elements e in list for which fn(e) returns true.

Example:

scala> filter((x: Int) => x % 2 == 0, List(1,2,3,4))
res7: List[Int] = List(2, 4)

def reduce[T](fn: (T, T) => T, list: List[T]): T

Return a new value of type T which results from applying fn successively to the elements of list as follows:

  1. Use list(0) as an initial accumulator value, accum.
  2. Apply fn(accum, list(i)) for i = 1 to produce a new accum value.
  3. Repeat Step 2 for $i = 2 .. list.length - 1$.
  4. Return the final value of accum as the result value of the reduction.

Note that the explanation above uses indexes to be clear about the process, but you may not use index operations. Here’s another explanation of reduce using the recursive structure of lists:

Sarting with list.tail as the starting list lst and list.head as an accummulator value,

  1. If lst == Nil, return the accumulator
  2. Otherwise, recurse with list.tail as lst and fn(accum, list.head) as the accumulator value.

The description above probably gave it away. :)

reduce is a special case of fold for non-empty lists using list.head as the “zero” value and folding into list.tail. You’ll learn what this means later.

Example:

scala> reduce((x: Int, y: Int) => x + y, List(1,2,3,4))
res4: Int = 10

scala> reduce((x: String, y: String) => x + y, List("Honey", "Boo", "Boo"))
res5: String = HoneyBooBoo

concat[T](list1: List[T], list2: List[T]): List[T]

Return a new List which contains all the elements of list1 followed by all the elements of list2.

Example:

scala> concat(List(1,2,3), List(4,5,6))
res13: List[Int] = List(1, 2, 3, 4, 5, 6)

def merge[T](list1: List[T], list2: List[T])(implicit ordering: Ordering[T]): List[T]

Return a new List with all the elements in list1 and list2 but in ascending sorted order.

Note: to make the comparison of elements convenient using the < operator, you’ll need to use an advanced feature known as type classes. We’ll learn about type classes later, but for now, use this stub as a starter for your merge function:

def merge[T](list1: List[T], list2: List[T])(implicit ordering: Ordering[T]): List[T] = {
  import ordering.mkOrderingOps // This import adds <, >, etc. To instances of T
  ??? // The rest is up to you.
}

Example:

scala> merge(List(1,3,5), List(2,3,4))
res41: List[Int] = List(1, 2, 3, 3, 4, 5)

def mergeSort[T](list: List[T])(implicit ordering: Ordering[T]): List[T]

Return a new List with all the elements in list but in ascending sorted order using the merge sort algorithm. Merge sort is a recursive divide-and-conquer algorithm:

  1. If the list has 0 or 1 elements, it’s already sorted so return it.
  2. Otherwise:
    1. Divide the input list into two halves
    2. Recursively merge sort each half
    3. Merge the two halves into a single list by taking the “next” element in order from each list so the resulting merged list is in sorted order
    4. Return the merged list

To simplify the writing of this method, you may use the following List method on list:

You may also store intermediate values in vals. For example (hint!):

val left = list.take(list.length / 2)

Note that mergeSort is itself recursive. You don’t need a local helper function.

Example:

scala> merge(List(1,3,5), List(2,3,4))
res41: List[Int] = List(1, 2, 3, 3, 4, 5)

Tips and Considerations

Grading

20 points per function. That’s right, there’s 80 points of extra credit. But you’ll find the last 80 points quite challenging.

Turn-in Procedure

Submit your listutils.scala file on Canvas as an attachment. When you’re ready, double-check that you have submitted and not just saved a draft.

Verify the Success of Your Submission to Canvas

Practice safe submission! Verify that your HW files were truly submitted correctly, the upload was successful, and that your program runs with no syntax or runtime errors. It is solely your responsibility to turn in your homework and practice this safe submission safeguard. NOTE: Unlike TSquare, Canvas will not send an email indicating that your assignment has been submitted successfully. Follow the steps outlined below to ensure you have submitted correctly.