[PL] Introduction to Programming Languages Exercise 3

Exercise 3.1

Consider the following definition of Student:

case class Student(name: String, height: Int)

Implement a function names:

def names(l: List[Student]): List[String] = ??? 

that takes a list of students as an argument and returns a list containing the names of the students.

def names(l: List[Student]): List[String] = l match {
	case Nil => Nil
    case h :: t => h.name :: names(t)
}

Exercise 3.2

Consider the same definition of Student.
Implement a function tall:

def tall(l: List[Student]): List[Student] = ??? 

that takes a list of students as an argument and returns a list of students whose heights are greater than 170.

def tall(l: List[Student]): List[Student] = l match {
	case Nil => Nil
    case h :: t => 
    	if (h.height>170)
        	h :: tall(t)
        else
        	tall(t)
}
        

Exercise 3.3

Implement a function length:

def length(l: List[Int]): Int = ???

that takes a list of integers as an argument and returns the length of the list.
Note that there is a built-in method l.length, but try to implement by yourself with recursion.

def length(l: List[Int]): Int = l match {
	case Nil => 0
    case h :: t => 1 + length(t)
}

Exercise 3.4

Implement a function append:

def append(l: List[Int], n: Int): List[Int] = ???

that takes a list of integers and an integer as arguments and returns a list obtained by appending the integer at the end of the list. Then, compare the time complexity of appending a new element to that of prepending a new element by ::, which is (1).

Notethat there is a built-in method l.appended(n),but try to implement by yourself with recursion.

def append(l: List[Int], n: Int): List[Int] = l match {
	case Nil => n :: Nil
    case h :: t => h :: append(t, n)
}

It's time complexity is O(n).