These problems are not the distribution of what will be on the midterm, but should give you a good idea of what kinds of questions are on the exam, and good sample questions for the more difficult problems.
Define subList :: Eq a => [a] -> [a] -> Bool, which checks if one list is a sublist of another. subList lst’ lst should return True if every element of lst’ occurs in lst. Order and duplicates do not matter: [3,2,2] is a sublist of [1,2,3] even though the order is different and 2 appears twice in the first list.
(a) Define subList using recursion:
(b) Define subList using higher-order functions:
The following function uses an auxilliary function to test if a number is prime. The aux function takes a list of possible divisors and checks each one in turn. If none of the divisors are valid, it returns true.
isPrime :: Integer -> Bool
isPrime n =
let aux [] = True
aux (x:xs) = (n `mod` x /= 0) && (aux xs)
in aux [2..(n-1)]
Write a version of isPrime that uses higher-order functions instead of recursion. You do not have to use a helper function, but if you do make sure your helper function is not recursive. You may use multiple higher-order functions.
Write a function mostCommonElement :: Eq a => [a] -> a that takes a list and returns the most common element.
(a) Define a higher-order function exists :: (a -> Bool) -> [a] -> Bool that takes a predicate, a list, and returns True if the predicate is true for anything in the list.
(b) Using exists, define zeroDetector :: [Int] -> Bool to check if there is a zero in a list.
(c) Using exists, define isPrime :: Int -> Bool that takes an integer and returns True if it is prime (i.e. not evenly divisible by any number other than 1 and itself).
(a) Write a higher order function bucket :: Eq b => (a -> b) -> [b] -> [a] -> [[a]]
Where bucket f labels xs groups the elements of xs based on which elements of buckets they map to. For instance:
buckets (`mod` 3) [0,1,2] [6..10] = [[6,9],[7,10],[8]]
Groups the numbers for 6 to 10 based on their remainder when divided by 3. The first list ([6,9]) contains those with remainder 0, the list [7,10] remainder 1, and [8] remainder 2.
(b) The function radix :: Int -> Int -> Int takes an exponent a number, and returns the digit of that number in that exponent's place. For instance, radix 3 1972 returns 9, while
radix 1 1972 returns 2.
radix 1 n = n `mod` 10
radix k n = radix (k-1) (n `div` 10)
Using radix and bucket write the following three functions
radixHundreds :: [Int] -> [[Int]] that takes a list of integers and groups them by their hundreds digit.
radixTens :: [Int] -> [[Int]] that takes a list of integers and groups them by their tens digit.
radixOnes :: [Int] -> [[Int]]that takes a list of integers and groups them by their ones digit.
(c) Using the above functions, concat, and map, write a linear-time sorting algorithm for integers of 3 digits or less.
radixSort :: [Int] -> [Int]
Without using list comprehensions with multiple generators, write
crossProduct :: [a] -> [b] -> [(a,b)] that takes two lists and returns their cross product.
For instance,
crossProduct [1,2] "ABC" = [(1,'A'),(1,'B'),(1,'C'),(2,'A'),(2,'B'),(2,'C')]
For this problem, we consider lists that represent sets. Thus order does not matter, and you may assume there are no repeated elements. You may not use the powerset function, even if you implement it yourself.
Recall the subset relation: a list lst’ is a subset of lst if every element of lst’ occurs in lst. Thus [2,3] is a subset of [9,3,2], even though the elements are out of order.
The subset sum problem is, given a list of unique integers lst and a target value n, does there exist a subset of lst whose elements sum to value.
Define a function subsetSum:: Integer -> [Integer] -> Bool that checks if a subset of the list exists that sums to the integer. For example, subsetSum 4 [1,5,-6,10] is True, while
subsetSum 8 [1,5,-6,10] is False.