— CPSC 312 2021 Assignment 1 Solution
— Copyright David Poole 2021
— harmonic n evaluates to the nth harmonic number
harmonic 1 = 1
harmonic n = harmonic (n-1) + 1/n
— harmonic (length [1,2,3,4]) gives a type error; length returns an Int but harmonic needs a Fractional
— Use the following:
— harmonic (fromIntegral (length [1,2,3,4]))
— Note that _ is just a variable name; it is special in that it is a “don’t care” variable; it’s value is not used elsewhere in the code
— wins p nw nl probability of a team winning series given it has probability of p of winning each game;
— it needs nw wins to win series, and loses series if it loses nl games
wins :: Double -> Int -> Int -> Double
wins _ 0 _ = 1
wins _ _ 0 = 0
wins p nw nl = p*(wins p (nw-1) nl) + (1-p) * (wins p nw (nl-1))
— probability of winning a 5 game tournament if a team has a 0.6 probability of winning each game
— wins 0.6 3 3
— probability of winning a 7 game tournament if a team has a 0.6 probability of winning each game
— wins 0.6 4 4
— probability of winning a 7 game tournament if one team is up 2-1 and each team has even chance of winning each game
— wins 0.5 2 3
— Question 3
foo :: Int -> Int
foo x = x+3
dfoo x = foo (foo x)
nfoo x = x+3+3
fooeach [] = []
fooeach (h:t) = foo h : t
nfooeach [] = []
nfooeach (h:t) = nfoo h : t
iffoo [] = []
iffoo (h:t)
| h < 4.3 = h:t
| otherwise = t
dd x y = 2*x + 3*y + 7
--- inferred types
-- dfoo :: Int -> Int
— nfoo :: Num a => a -> a
— fooeach :: [Int] -> [Int]
— nfooeach :: Num a => [a] -> [a]
— iffoo :: (Ord a, Fractional a) => [a] -> [a]
— dd :: Num a => a -> a -> a
— dd 4.3 :: Fractional a => a -> a
— Question 4
— myreplace x y lst replaces all occurrences of x in lst with y
myreplace :: Eq t => t -> t -> [t] -> [t]
myreplace _ _ [] = []
myreplace x y (h:t) =
(if x==h then y else h) : myreplace x y t
— myreplace 7 3 [7,0,7,1,7,2,7,3]
— myreplace ‘a’ ‘x’ “”
— myreplace ‘a’ ‘x’ “abacad”
— myapply lst sub where sub is a list of (x,y) pairs, replaces each occurrence of x by y in lst.
myapply :: Eq t => [t] -> [(t, t)] -> [t]
myapply [] _ = []
myapply (h:t) sub = app h sub :myapply t sub
where
— app e sub gives the value e is replaced by according to sub
app e [] = e
app e ((x,y):r)
| e==x = y
| otherwise = app e r
— myapply “abcdec” [(‘a’,’f’), (‘c’,’3′), (‘g’,’7′)]
— myapply “baab” [(‘a’,’b’), (‘b’,’a’)]
— myordered lst is True if lst is ordered.
myordered :: Ord t => [t] -> Bool
myordered [] = True
myordered [e] = True
myordered (a:b:r) = a <= b && myordered (b:r)
-- Try
-- myordered "abcdefg"
-- myordered "ba"
-- myremoveduplicates lst removes duplicates from a list; returns a list with
-- the same elements as lst, but with only one instance of each element
myremoveduplicates :: Eq t => [t] -> [t]
myremoveduplicates [] = []
myremoveduplicates (e1:r)
| elem e1 r = myremoveduplicates r
| otherwise = e1 : myremoveduplicates r
— Try:
— myremoveduplicates “abacad”
— myremoveduplicates [7,3,2,1,3,2,2,1,1,3,7,8]
myremoveduplicatesfirst :: Eq t => [t] -> [t]
myremoveduplicatesfirst lst = remdupfirst lst []
where
— remdupfirst lst1 lst2 returns the elements in lst1 without duplicates that are not in lst2
remdupfirst [] _ = []
remdupfirst (h:t) lst2
| h `elem` lst2 = remdupfirst t lst2
| otherwise = h : remdupfirst t (h:lst2)
— Try:
— myremoveduplicatesfirst “abacad”
— myremoveduplicatesfirst [7,3,2,1,3,2,2,1,1,3,7,8]
— deln n e lst returns the list that results from deleting the first n occurrences of e from lst
deln :: Eq t => Int -> t -> [t] -> [t]
deln 0 _ lst = lst
deln n e [] = []
deln n e (h:t)
| e==h = deln (n-1) e t
| otherwise = h:deln n e t
— deln 2 ‘a’ “avatar”
— delna n e lst returns a list of all of the lists that result from deleting exactly n occurrences of e from lst
— You should write you own ++
delna :: Eq t => Int -> t -> [t] -> [[t]]
delna 0 _ lst = [lst]
delna n e [] = []
delna n e (h:t)
| e==h = (delna (n-1) e t) ++ cons_to_each h (delna n e t)
| otherwise = cons_to_each h (delna n e t)
where
— cons_to_each e lst — adds e to the front of every element of lst
— note that adding an element to the front of a list is often called “cons” from the Lisp function
cons_to_each _ [] = []
cons_to_each e (h:t) = (e:h):cons_to_each e t
— delna 2 ‘a’ “avatar”
— Note that this is easier with map
delna1 :: Eq t => Int -> t -> [t] -> [[t]]
delna1 0 _ lst = [lst]
delna1 n e [] = []
delna1 n e (h:t)
| e==h = (delna1 (n-1) e t) ++ map (h:) (delna1 n e t)
| otherwise = map (h:) (delna1 n e t)
— delna1 2 ‘a’ “avatar”
— Note that this would be easier with list comprehensions(?)
delna2 :: Eq t => Int -> t -> [t] -> [[t]]
delna2 0 _ lst = [lst]
delna2 n e [] = []
delna2 n e (h:t)
| e==h = (delna2 (n-1) e t) ++ [h:r | r <- delna2 n e t]
| otherwise = [h:r | r <- delna2 n e t]
-- delna2 2 'a' "avatar"