Three Homework Problems
May 3, 2019
The end of the school year is approaching in many places, and students are submitting their final homework assignment, so they ask questions on the internet. Here are three questions I have seen recently:
- Write a function
adjoin-setthat given a set of integers stored in a linked list in increasing order, and an integer to be inserted in the set, adjoins the integer to the set if it is not already in the set and returns the updated set. - Write a function
list-indexthat finds the index within a list where a given item occurs, or returns -1 if the item is not in the list. - Write a function
update-countthat takes a list of key/count pairs and a key and increments the count of the given key, or adds a new key/count pair with count = 1 if the key is not present in the list.
Your task is to solve the three problems posed above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
A Haskell version using direct recursion and no library functions.
-- adjoinSet x ys is ys if x is already an element of ys, otherwise it's ys with -- x preceding the first element greater than it. If x is greater than all -- elements of ys it then the result will be ys with x appended to the end. adjoinSet :: Ord a => a -> [a] -> [a] adjoinSet x [] = [x] adjoinSet x (y:ys) | x < y = x : y : ys | x == y = y : ys | otherwise = y : adjoinSet x ys -- listIndex x ys is the 0-based index of the first occurence of x in ys, or -1 -- if x doesn't occur in ys. listIndex :: Eq a => a -> [a] -> Int listIndex x = go 0 where go _ [] = -1 go i (y:ys) | x == y = i | otherwise = go (i+1) ys -- updateCount x ys is ys, except that the count of the first entry whose key -- equals x has been incremented by one. If no key equals x then it is ys with -- (x,1) appended to the end. updateCount :: (Eq a, Integral b) => a -> [(a,b)] -> [(a,b)] updateCount k' [] = [(k',1)] updateCount k' ((k,c):kcs) | k' == k = (k,c+1) : kcs | otherwise = (k,c) : updateCount k' kcs main :: IO () main = do print $ adjoinSet 5 [] print $ adjoinSet 5 [1..3] print $ adjoinSet 5 [1..6] print $ adjoinSet 5 [7..9] print $ listIndex 5 [] print $ listIndex 5 [1..3] print $ listIndex 5 [1..6] print $ updateCount 5 [] print $ updateCount 5 [(1,1),(2,2),(3,3)] print $ updateCount 5 [(1,1),(2,2),(3,3),(4,4),(5,5),(6,6)]