Drill 9 Solution

Question 1

Given this function:

fun list-len(lst :: List)-> Number:
  cases(List) lst:
  | empty => 0
  | link(first, rest) => 1 + list-len(____)
  end
end

Fill in the blank so that list-len correctly calculates the length of lst.

Answer

rest

In order to calculate the length of lst, we add 1 to the length of the rest of lst.

Question 2

Given this function:

fun list-product(lst :: List)-> Number:
  cases(List) lst:
  | empty => 1
  | link(first, rest) => ____ * list-sum(rest)
  end
end

Fill in the blank so that list-sum correctly computes the product of all the value in lst.

Answer

first

To get the product of all the values in lst we multiply first by the product of the rest of lst.

Question 3

Is

link(3, 4)

a valid list?

( ) Yes
( ) No

Answer

( ) Yes
(X) No

No–the second argument of link needs to be of type List.

Question 4

Given this code:

fun is-member(lst :: List, item :: Number)-> Boolean:
 cases(List) lst:
 | empty => Blank1
 | link(first, rest) => (first == Blank2) or (is-member(Blank3, Blank4)
  end
end

Fill in the blanks such that is-member correctly returns true if item is a member of lst, and false if otherwise.

Blank1: ____

Blank2: ____

Blank3: ____

Blank4: ____

Answer

Blank1: false

Blank2: item

Blank3: rest

Blank4: item

If lst is empty, then the function has finished going though the entire list and returns false. Otherwise, the functions checks if first is equal to item. If it is, the function returns true, otherwise it makes a recursive call on the rest of the list.