Review for Quiz 3

One-page version suitable for printing.

Question 3-1

Write a Haskell function log2 that takes a parameter n and returns the number of times you can divide n by 2 before reaching 1. For example, log2 25 should return 4, since it takes 4 divisions of 100 until we reach 1:

25 div 2 = 12
12 div 2 = 6
6 div 2 = 3
3 div 2 = 1

Solution

Question 3-2

Write a Haskell function everyOther which takes a list and returns a list containing every other element of it. For example, everyOther [1..10] should return the list [1,3,5,7,9]. Your function should be able to work for lists of any length (whether even or odd).

Solution

Question 3-3

Write a Haskell function select, which takes a list indices of integers (which you may assume is in increasing order) and another list data, and it returns the items of data at the indices mentioned in indices. For example, select [1,2,4] [10..20] would return [11,12,14], since 11 is at position 1 in the list [10..20] (we start numbering positions from 0), 12 at position 2, and 14 at position 4. Your function should be able to work in O(n) time, where n is the length of data.

Solution

Question 3-4

Simplify the following lambda expression to normal form. Show your intermediate steps.

(((\f.\g.g f) (\x.10 - x)) (\y.\x.y (y x))) 4

Solution