-- | First assignment for IB016, semester sprint 2015
-- Name: Martin Ukrop
-- UID: 374297

module Polynomial (
    -- * Polynomial type
      Polynomial (..)
    -- * Printing
    , polyPrint
    -- * Evaluation
    , eval
    , belongs
    -- * Properties
    , yIntersect
    , quadratic
    -- * Operations
    , scalarTimes
    , polyPlus
    , polyMinus
    , polyTimes
    ) where

-- | The Polynomial type. Polynomials are represented as a list of coefficients
-- of increasing power. That is, the first element of list is constant element,
-- the second is the coefficient for x, the third coefficient for x^2 and so on.
-- There should be no trailing zeroes in the polynomial representation, i.e.
-- x^2 + 2x + 3 is represented as @'P' [3,2,1]@ not @'P' [3,2,1,0,0]@ or similar.
newtype Polynomial a = P { unP :: [a] } deriving Show

-- | Evaluate polynomial in given value. This can be viewed as
-- converting the polynomial to the evaluation function.
--
-- >>> eval (P [3, 1, -5]) 2
-- -15
eval :: Num a => Polynomial a -> a -> a
eval (P poly) val = sum . zipWith (*) poly $ iterate (*val) 1

-- | Determines, if a given point belongs to the polynomial.
--
-- >>> belongs (2, -15) (P [3, 1, -5])
-- True
belongs :: (Num a, Eq a) => (a, a) -> Polynomial a -> Bool
belongs (x,y) poly = y == eval poly x

-- | Determines, if the polynomial is quadratic
--
-- >>> quadratic (P [1, 2, -1])
-- True
quadratic :: Polynomial a -> Bool
quadratic = (==3) . length . unP

-- | Find the coordinates of the polynomial intersecting the y axis.
--
-- >>> yIntersect (P [1, 2, -1])
-- (0, 1)
yIntersect :: Num a => Polynomial a -> (a, a)
yIntersect (P []) = (0, 0)
yIntersect (P (x:_)) = (0, x)

-- | Print polynomial into pretty string representation.
--
-- The first argument is the variable name. Write spaces in between the term
-- operators. Coefficients 1 and -1 should be diplayed only as a sign symbol.
-- Do not display terms with zero coefficients.
--
-- >>> polyPrint "x" (P [1, 2, 3, 4])
-- "4x^3 + 3x^2 + 2x + 1"
-- >>> polyPrint "x" (P [-1, 0, -1, 3, -4])
-- "- 4x^4 + 3x^3 - x^2 - 1"
-- polyPrint "x" (P [0, 0, -1])
-- "- x^2"
-- polyPrint "x" (P [])
-- "0"
polyPrint :: (Num a, Ord a, Show a) => String -> Polynomial a -> String
polyPrint _ (P []) = "0"
polyPrint var (P poly) = tail . concat . topTerm . map textualize . reverse . absTerm $ zip poly vars
  where topTerm ((' ':'+':' ':term):xs) = (' ':term):xs
        topTerm xs = xs
        textualize (n, str)
          | n > 1 = " + " ++ show n ++ str
          | n == 1 = " + " ++ str
          | n == 0 = ""
          | n == -1 = " - " ++ str
          | otherwise = " - " ++ show (abs n) ++ str
        absTerm ((1,_):xs) = (1,"1"):xs
        absTerm ((-1,_):xs) = (-1,"1"):xs
        absTerm xs = xs
        vars = "" : var : map (\n -> var ++ "^" ++ show n) [(2::Int)..]

-- | Remove trailing zeroes from the unnormalized polynomial.
normalize :: (Num a, Eq a) => Polynomial a -> Polynomial a
normalize = P . reverse . dropWhile (== 0) . reverse . unP

-- | Multiply scalar and polynomial.
--
-- >>> scalarTimes 3 (P [1, 2, 3])
-- P [3, 6, 9]
-- >>> scalarTimes 0 (P [1, 2, 3])
-- P []
scalarTimes :: (Eq a, Num a) => a -> Polynomial a -> Polynomial a
scalarTimes a (P poly) = normalize . P $ map (*a) poly

-- | Sum two polynomials.
--
-- >>> polyPlus (P [1, 2, 3]) (P [2, 2, -3])
-- P [3, 4]
polyPlus :: (Num a, Eq a) => Polynomial a -> Polynomial a -> Polynomial a
P x `polyPlus` P y = normalize . P $ zipWith (+) (x ++ pad) (y ++ pad)
        where pad = replicate (max (length x) (length y)) 0

-- | Make a difference of two polynomials.
--
-- >>> polyMinus (P [2, -5, 3, 3]) (P [1, 2, 3])
-- P [1, -7, 0, 3]
polyMinus :: (Num a, Eq a) => Polynomial a -> Polynomial a -> Polynomial a
polyMinus x y = x `polyPlus` scalarTimes (-1) y

-- | Multiply two polynomials.
--
-- >>> polyTimes (P [2, 1]) (P [2, 3])
-- P [4, 8, 3]
polyTimes :: (Num a, Eq a) => Polynomial a -> Polynomial a -> Polynomial a
P [] `polyTimes` _ = P []
P x `polyTimes` yy = foldr1 polyPlus . zipWith scalarTimes x $ iterate shift yy
  where shift (P poly) = P (0:poly)