Three Homework Problems
May 3, 2019
All of these are solved by scanning through the list.
- 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)))))) - 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)))))) - 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.
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)]