We defined lists in the class. Write a recursive procedure to get the nth element of the list or throw an IllegalArgumentException if n <0 or n >= length of list. Assume n = 0 obtains the very first element and n = length of list - 1 yields very last element. 1 sealed trait NumList case object Nil extends NumList case class Cons(n: Int, l: NumList) extends NumList def getNthElement(lst: NumList, n: Int): Int = { ??? // YOUR CODE HERE B (7 points) Write a recursive procedure that returns true if the list has the Fibonacci property. I. e, every element at position i > 2 is the sum of the two preceding elements. Note that the property is trivially true for lists of sizes 0 and 1. 1 def isFibonacciList (lst: NumList): Boolean = { ??? // YOUR CODE HERE 3 } C (8 points) Write a recursive function filterNumList(l: NumList, f: Int => Boolean): NumList that takes in a NumList and a function f: Int => Boolean. 1. It should return a new list that consist of all elements of the list i that return true when the function f is called on them. 2. The returned list elements must preserve the same order as in the original list. 1 ??? // YOUR CODE HERE

Answer and Explanation:

•Code:

A:

sealed trait NumList

case object Nil extends NumList

case class Cons(n: Int, l: NumList) extends NumList

def listLength(lst: NumList): Int = {

lst match { // pattern match the lst

case Nil => 0

case Cons(_, tl) => 1 + listLength(tl) // _ here is to tell scala that I do not care what is the element.

}

}

def getNthElement(lst: NumList, n: Int): Int = {

// YOUR CODE HERE

val l = listLength(lst)

lst match {

case _ if(n < 0 || n >= l) => throw new IllegalArgumentException("n is negative")

case Cons(_, rest) if (n != 0) => getNthElement(rest, n-1)

case Cons(ret, rest) if (n == 0) => ret

}

}

A - output:

defined trait NumList

defined object Nil

defined class Cons

defined function listLength

defined function getNthElement

A - Testing:

// BEGIN TESTS

val l1 = Nil

val l2 = Cons(1, Cons(-1, Nil))

val l3 = Cons(1, Cons(2, l2))

val l4 = Cons(0, Cons(4, Cons(8, l3)))

val test1 = try {

getNthElement(Nil, 3);

assert(false, "Test 1 : getNthElement(Nil, 3) should raise an IllegalArgumentException. Your code did not.")

} catch {

case e: IllegalArgumentException => "OK"

}

assert(getNthElement(l2, 0) == 1, "Test2: getNthElement(l2, 0) failed (expected answer = 1)")

assert(getNthElement(l3, 3) == -1, "Test3: getNthElement(l3, 3) failed (expected answer = -1)")

assert(getNthElement(l4, 2) == 8, "Test4: getNthElement(l4, 2) failed (expected answer = 8)")

val test2 = try {

getNthElement(l4, 8);

assert(false, "Test 5 : getNthElement(l4, 8) should raise an IllegalArgumentException. Your code did not.")

} catch {

case e: IllegalArgumentException => "OK"

}

// END TESTS

TEST output:

l1: Nil.type = Nil

l2: Cons = Cons(1,Cons(-1,Nil))

l3: Cons = Cons(1,Cons(2,Cons(1,Cons(-1,Nil

l4: Cons = Cons(0,Cons(4,Cons(8,Cons(1,Cons(2,Cons(1,Cons(-1,Nil

test1: Any = OK

test2: Any = OK  

Answer B:

def isFibonacciList(lst: NumList): Boolean = {

// YOUR CODE HERE

val l = listLength(lst)

lst match {

case _ if(l <= 2) => true

case Cons(one, Cons(two, Cons(three, rest))) if(one + two == three) => {

isFibonacciList(Cons(two, Cons(three, rest)))

}

case Cons(one, Cons(two, Cons(three, rest))) if(one + two != three) => {false}

}

}

B-output:

defined function isFibonacciList  

B-Testing:

// BEGIN TESTS

val l1 = Cons(12, Cons(25, Cons(37, Nil)))

assert(isFibonacciList(l1),

"Test case 1 : isFibonacciList(l1) -- should return true")

val l2 = Cons(14, Cons(-1, Cons(13, l1 )))

assert(isFibonacciList(l2),

"Test case 2 : isFibonacciList(l2) -- should return true")

val l3 = Cons(7, Cons(7, l2))

assert(!isFibonacciList(l3),

"Test case 3 : isFibonacciList(l3) -- should return false")

val l4 = Cons(0, Cons(0, Cons(0, Cons(0, Cons(0, Cons(0, Nil

assert(isFibonacciList(l2),

"Test case 4: isFibonacciList(l4) -- should return true")

// END TESTS

Test output:

l1: Cons = Cons(12,Cons(25,Cons(37,Nil)))

l2: Cons = Cons(14,Cons(-1,Cons(13,Cons(12,Cons(25,Cons(37,Nil

l3: Cons = Cons(7,Cons(7,Cons(14,Cons(-1,Cons(13,Cons(12,Cons(25,Cons(37,Nil

l4: Cons = Cons(0,Cons(0,Cons(0,Cons(0,Cons(0,Cons(0,Nil  

Answer C:

def filterNumList(l: NumList, f: Int => Boolean): NumList = {

l match {

case Nil => Nil

case Cons(first, rest) => {

if (f(first)){

Cons(first, filterNumList(rest, f))

}

else {

filterNumList(rest, f)

}

}

}

}

C - output:

defined function filterNumList  

C - Testing:

// BEGIN TESTS

val l1 = Cons(12, Cons(25, Cons(37, Nil)))

def f1(j: Int): Boolean = j <= 25 && j >= 12

assert(filterNumList(l1, f1) == Cons(12, Cons(25, Nil)), "Test 1 failed.")

val l2 = Cons(22, Cons(135, Cons(137, l1)))

def f2(j: Int): Boolean = j % 5 == 0

assert(filterNumList(l2, f2) == Cons(135, Cons(25, Nil)), "Test 2 failed.")

def f3(j: Int): Boolean = j >= 210

assert(filterNumList(l2, f3) == Nil, "Test 3 failed.")

assert(filterNumList(Nil, f3) == Nil, "Test 4 failed.")

val l4 = Cons(0, Cons(0, Cons(0, Cons(0, Cons(0, Cons(0, Nil

def f4(j: Int): Boolean = j <= 0

assert(filterNumList(l4, f4) == l4, "Test 5 failed")

// END TESTS

Test output:

l1: Cons = Cons(12,Cons(25,Cons(37,Nil)))

defined function f1

l2: Cons = Cons(22,Cons(135,Cons(137,Cons(12,Cons(25,Cons(37,Nil

defined function f2

defined function f3

l4: Cons = Cons(0,Cons(0,Cons(0,Cons(0,Cons(0,Cons(0,Nil

defined function f4

answer:

31

explanation: