Solution HW04 of CIS 194 Haskell course 2015
{-# OPTIONS_GHC -Wall #-}
module HW04 where
import Data.List
newtype Poly a = P [a]
-- Exercise 1 ----------------------------------------getCoefs :: Poly a -> [a]
getCoefs (P p) = p
lengthPoly :: Poly a -> Int
lengthPoly (P p) = length p
x :: Num a => Poly a
x = P [0,1]
-- Exercise 2 ---------------------------------------normalize :: (Num a, Eq a) => [a] -> [a]
normalize [] = [0]
normalize (t:ts) = t : dropWhileEnd (==0) ts
normalizeP :: (Num a, Eq a) => Poly a -> Poly a
normalizeP (P p) = P $ normalize p
instance (Num a, Eq a) => Eq (Poly a) where
(==) (P p1) (P p2) = np1 == np2 where
np1 = normalize p1
np2 = normalize p2
-- Exercise 3 ----------------------------------------instance (Num a, Eq a, Show a) => Show (Poly a) where
show mp = pShow (reverse np) where
(P np) = normalizeP mp
pShow [] = "0"
pShow [0]
| length np > 1 = ""
| otherwise = "0"
pShow [c] = show c
pShow (coef:cs) = termShow coef (length cs) ++ plusShow coef cs ++ pShow cs
where
plusShow 0 _ = ""
plusShow _ (0:_) = ""
plusShow _ _ = " + "
termShow 0 _ = ""
termShow 1 1 = "x"
termShow 1 n = "x^" ++ (show n)
termShow c 1 = (show c) ++ "x"
termShow c n = (show c) ++ "x^" ++ (show n)
-- Exercise 4 ----------------------------------------pad :: Num a => [a] -> Int -> [a]
pad p n
| n <= l = p
| otherwise = p ++ (replicate (n-l) 0)
where l = length p
padP :: Num a => Poly a -> Int -> Poly a
padP (P p) n = P $ pad p n
plus :: Num a => [a] -> [a] -> [a]
plus p1 p2 = zipWith (+) (pad p1 n) (pad p2 n)
where
n = max (length p1) (length p2)
plusP :: Num a => Poly a -> Poly a -> Poly a
plusP (P p1) (P p2) = P $ plus p1 p2
-- Exercise 5 ----------------------------------------shift :: Num a => [a] -> Int -> [a]
shift p n = (replicate n 0) ++ p
shiftP :: Num a => Poly a -> Int -> Poly a
shiftP (P p) n = P $ shift p n
times :: Num a => [a] -> [a] -> [a]
times p1 p2
| length p1 > length p2 = times p2 p1
| otherwise = foldl plus [0] allterms
where
allterms = fst $ foldl (f p2) ([], 0) p1
f p (terms, degree) n = (newterms, degree + 1)
where newterms = (map (n*) newp) : terms
newp = shift p degree
timesP :: Num a => Poly a -> Poly a -> Poly a
timesP (P p1) (P p2) = P $ times p1 p2
-- Exercise 6 ----------------------------------------instance Num a => Num (Poly a) where
(+) = plusP
(*) = timesP
negate (P p) = P $ map ((-1)*) p
fromInteger n = P $ [fromInteger n]
-- No meaningful definitions exist
abs = undefined
signum = undefined
-- Exercise 7 ----------------------------------------apply :: Num a => [a] -> a -> a
apply p n = fst $ foldl f (0, 0 :: Int) p where
f (result, degree) coef = (result + coef * n ^ degree, degree + 1)
applyP :: Num a => Poly a -> a -> a
applyP (P p) n = apply p n
-- Exercise 8 ----------------------------------------class Num a => Differentiable a where
deriv :: a -> a
nderiv :: Int -> a -> a
nderiv 0 = id
nderiv 1 = deriv
nderiv n
| n > 0 = deriv . (nderiv $ n-1)
| otherwise = undefined
-- Exercise 9 ----------------------------------------instance Num a => Differentiable (Poly a) where
deriv (P p) = P $ derivL p where
derivL [] = [0]
derivL [_] = [0]
derivL (_:cs) = fst $ foldl f ([], 1) cs where
f (dp, degree) coef = (dp ++ [coef * degree], degree+1)
