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 ⌊log2(n)⌋, where ⌊x⌋ denotes the floor function, i.e. rounding down to the nearest integer.

7. 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.

8. 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.

9. 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]

10. 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

11. Cyclic List

Implelement the built-in function cycle that takes a list L and returns an infinite list consisting of L repeated over and over:

> take 10 (cycle "abc")
"abcabcabca"

12. Sorting

For each of the following algorithms, write a function that uses the algorithm to sort a list of integers.

  1. insertion sort

  2. selection sort

  3. merge sort

  4. quicksort

14. All Pairs

Construct an infinite list allPairs that contains all pairs of positive integers. Every pair must appear exactly once in the list.

15. Prime

Write a function that determines whether an integer is prime.

16. All Primes

Construct an infinite list containing all prime numbers.