Three Homework Problems

May 3, 2019

All of these are solved by scanning through the list.

  1. We scan through the linked list to find the spot where the new item belongs, and add it if it is not already present in the list:
    (define (adjoin-set x xs)
      (let loop ((xs xs) (zs (list)))
        (cond ((null? xs) (reverse (cons x zs)))
              ((= x (car xs)) (append (reverse zs) xs))
              ((< x (car xs)) (append (reverse (cons x zs)) xs))
              (else (loop (cdr xs) (cons (car xs) zs))))))
  2. This is another scan through the input list. Since the list is not necessarily ordered, all we can do is compare equality at each item in the list. We assume the list items are integers, even though the problem did not specify:
    (define (list-index x xs)
      (let loop ((xs xs) (idx 0))
        (if (null? xs) -1
          (if (= (car xs) x) idx
            (loop (cdr xs) (+ idx 1))))))
  3. This is similar to the other two:
    (define (update-count k kc-pairs)
      (let loop ((kc-pairs kc-pairs) (zs (list)))
        (cond ((null? kc-pairs) (cons (cons k 1) zs))
              ((equal? (caar kc-pairs) k)
                (cons (cons (caar kc-pairs) (+ (cdar kc-pairs) 1))
                      (append (cdr kc-pairs) zs)))
              (else (loop (cdr kc-pairs) (cons (car kc-pairs) zs))))))

You can run the program at https://ideone.com/mo77gV.

Advertisements

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: