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

One Response to “Three Homework Problems”

  1. Globules said

    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 Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: