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:

  1. Write a function adjoin-set that 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.
  2. Write a function list-index that finds the index within a list where a given item occurs, or returns -1 if the item is not in the list.
  3. Write a function update-count that 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.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
1 Comment »

One Response to “Three Homework Problems”

  1. Globules said
    May 4, 2019 at 1:20 AM

    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)]

    $ ./homework3
[5]
[1,2,3,5]
[1,2,3,4,5,6]
[5,7,8,9]
-1
-1
4
[(5,1)]
[(1,1),(2,2),(3,3),(5,1)]
[(1,1),(2,2),(3,3),(4,4),(5,6),(6,6)]

Leave a comment