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. Power of Two

Write a function is_pow2 that determines whether a non-negative integer is a power of 2.

6. Bit Count

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

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

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

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

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

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

12. Fibonacci Numbers

Construct an infinite list containing all Fibonacci numbers: 1, 1, 2, 3, 5, 8, 13, ...

13. Even Fibonacci Numbers

Solve Project Euler's problem 2.

14. Prime

Write a function that determines whether an integer is prime.

15. All Primes

Construct an infinite list containing all prime numbers.

16. Largest Prime Factor

Solve Project Euler's problem 3.

17. Palindrome

Write a function that determines whether an Integer is a palindrome. For example, 46264 is palindromic. Do not use any strings in your solution.