Final Sample Problems

Here are sample problems for the final. The radix and crossProduct problems on the midterm sample problems are also appropriate.

1. Write a function middle :: Ord a => [a] -> a that takes a list of ordered types, and returns "middle" element: the one that has an equal number of larger and smaller elements. If there is no precisely middle element (because the list is of even length), you may return either of the two elements closest to the middle. You may use built-in functions. For instance:

middle [7,3,1,9,5] = 5
middle "flamingo" = 'l'
middle [1,2,3,4] = 2 //3 is also acceptable.

Note: this would not be a a good question for the final, because it is very easy using built-in functions and very hard using recursion.

2. Write an IO action getPassword :: IO (Maybe String) that prompts a user to enter a password, asks them to confirm the password, and returns that string if the two entries are equal. If they are not equal return Nothing.

3. Using either do blocks or case expressions, write a function

quadruple :: (Maybe a) -> (Maybe b) -> (Maybe c) -> (Maybe d) -> Maybe (a,b,c,d)

that takes 4 Maybe values. If any of them are Nothing, return nothing. Otherwise make a quadruple (4-tuple) of the values. 

4. Write a higher-order function myPartition :: Ord a => (a -> Bool) -> [a] -> ([a], [a]) that takes a Boolean predicate, a list of elements, and returns the tuple of two lists: the first containing all elements that make the predicate True, and the second all the elements that make the predicate False. For example:

myPartition isDigit "h3110, 1 @m l337 h4ck3r"  = ("31101133743", "h,  @m hckr")

5. A node-valued binary search tree is a tree where nodes carry values, that obeys the invariant that for a node with value x, all values in the left child are less than x, and all values in the right child are greater than x. 

data BST a = Node (BST a) a (BST a) | Leaf deriving Show

We say a binary search tree is balanced when, for every node, the number of left children is within 1 of the number of right children. Using middle, myPartition, delete, null, and non-structural recursion, write buildBalancedTree :: Ord a => [a] -> BST a that creates a balanced binary search tree from a (finite) list of elements. You may assume there are no duplicate elements. You may not pattern match on lists for this problem. 

You may benefit from a few built-in functions: null :: [a] -> Bool takes a list and returns True if the list is empty, and delete :: Eq a => a -> [a] -> [a] takes an element and a list, and removes the first occurrence of the element from the list.

Note: This is also an bad question for the final, as it incorporates BST's (which we didn't cover) and has awkward restrictions on recursion.

6. An "algebraic" type is one that supports a binary operation with an identity element. For instance integers, multiplication, and 1 are algebraic as x*1=x for every x. Integers and addition are also algebraic, but have the identity elements 0.

1. 1. • Define a typeclass for Algebraic types.

      • Make Strings an instance of the Algebraic typeclass, using concatenation as the binary operation.

      • An element n in an algebra is called "zero" when n*x=n for every x. (We here use * for whatever the operation in the algebra is.) Write a function hasZero (Eq a, Algebraic a) => [a] -> Bool that takes all (relevant) elements of a type and returns True if any of them are a zero element.

Note: On the final you will not be asked to do all three of these. You will either define the typeclass or make instances of it, but not both. Either may be combined with making a function that uses the typeclass, or that may be its own problem.

7. Decompose this problem into logically coherent subproblems, and describe how to solve the problem using the subproblems.

The problem is to write kMeans, which takes an integer k, a list of points, and returns a list of k clusters. A cluster is a center, which may not be an original point, and a list of points associated with the center. The list of clusters must: (a) contain all original points, (b) associate each point with the nearest center, and (c) have the center be in the middle of it's associated points.

You are given these type signatures
type Point = (Int, Int)
type Cluster = (Point, [Point])

And a distance function
dist :: Point -> Point -> Double

The algorithm to implement is:

• • • • Start with n points.

      • Take k points as starting centers.

      • Assign each point to its nearest center, forming the initial clusters.

      • Repeatedly improve the clusters by:

        • Update each center to be the mean of its cluster.

        • Assign each point to the nearest updated center

      • The algorithm terminates when the clusters stop changing.

(a) Write a function to solve this problem, using at least 4 helper functions that solve logical sub-problems. You do not need to define the helper functions.

kMeans:: Int -> [Point] -> [Cluster]

(b) For each helper function, provide it’s type and a brief description of what it does.