Week 6: Exercises

1. Last Element

Write a function lastElem that returns the last element of a list.

> lastElem [2, 4, 6, 8]
8

2. Second Last

Write a function secondLast that returns the second-to-last element of a list.

> secondLast [2, 4, 6, 8]
6

3. k-th element

Write a function kth k l that returns the kth element of a list l, where elements are numbered starting from 0. (Do not use the built-in operator !!, which does the same thing.)

4. Delete

Write a function del n l that deletes the first occurrence of an integer n from a list of integers l, returning a new list. If n is not present in the list, the function should return l unchanged.

5. Bit Count

Write a function bitCount that takes a non-negative Integer and returns the number of ones in its binary representation.

6. Log Base 2

Write a function log2 that takes a positive integer n and returns ⌊log₂(n)⌋, where ⌊x⌋ denotes the floor function, i.e. rounding down to the nearest integer.

7. Reverse

Write a function rev :: [a] -> [a] that reverses a list of any type. What is your function's running time as a function of N, the length of the input list?

8. Lexicographic Comparison

Write a function before that takes two strings s and t and returns True if s comes before t in dictionary order. In your function, you may use the operator < on characters, but not on strings.

9. Zip

Write a function zipper that converts two lists into a list of pairs:

> zipper [10, 12, 14] [21, 23, 25, 27]
[(10,21),(12,23),(14,25)]

Stop zipping when you reach the end of either list.

10. Unzip

Write a function unzipper that converts a list of pairs into a pair of lists:

> unzipper [(10, 21), (12, 23), (14, 25)]
([10,12,14],[21,23,25])

11. Association List

An association list is a list of key-value pairs representing a mapping from keys to values. For example, the association list [("red", 3), ("blue", 4)] maps "red" to 3 and "blue" to 4.

a) Write a function lookup that takes an association list and a key, and returns the corresponding value. If the key is not the list, throw an error. Give your function an appropriate type.

b) Write a function update that takes an association list, a key K, and a value V. If the key K is already present in the list, the function should update its value to be V; otherwise, the function should add a mapping from K to V.

12. Deduplicate

Write a function dedup that eliminates consecutive duplicate elements in a list of integers:

> dedup [2, 4, 4, 4, 6, 6, 8, 4]
[2, 4, 6, 8, 4]

13. Or

Which of these functions is equivalent to the built-in operator || ?

1. my_or a b = a || b

2. my_or a b = b || a

3. my_or _ True = True
my_or True _ = True
my_or _ _ = False

4. my_or True False = True
my_or True True = True
my_or False True = True
my_or False False = False