Haskell: Understanding algebraic data types better

Question

I'm trying to construct an algebraic data type that represents polynomials. Given the definition that an Integer constant is a polynomial and that if you add two polynomials or multiply two polynomials, it results in a polynomial.

I'm having a difficult time understanding how algebraic data types work in general and how I would even go about producing this. I currently have

data Poly = Const Int | 
            Add Poly Poly | 
            Mult Poly Poly

However I don't know what this even means or how to use it, I'm simply going off of examples I've seen of algebraic data types.

I've seen types like

data Tree = NullT |
            Node Int Tree Tree

That makes more sense to me, and how to use it. The polynomial example seems so abstract I don't know where to start.

Edit: When I try to implement simple testing functions like:

evalPoly :: Poly -> Int
evalPoly (Const n) = n

I'm met with the error

*Polynomial> evalPoly Poly 1

<interactive>:25:10: Not in scope: data constructor ‘Poly’
*Polynomial> 

Edit again: Thank you for all your suggestions and help, it's helped me produce something that's working for my purposes!

Answer 1

You seem to want to make an ADT for polynomials, but I'd prefer to use a Map. First some imports:

import qualified Data.Map as M
import Data.Function (on)

A polynomial is a Map from powers of x to coefficients.

newtype Poly a n = Poly {coeffMap :: M.Map n a} deriving (Show)
lift f = Poly . f . coeffMap

Let's make some simple polynomials:

zero = Poly M.empty                  -- none of the powers have non-zero coefficients
x = Poly $ M.singleton 1 1           -- x^1 has coefficient 1

constant 0 = zero
constant a = Poly $ M.singleton 0 a  -- x^0 has coefficient a

A standard thing to do with a polynomial is evaluate it with a particular value for x.

The fold here takes the partially-calculated b and adds on the new term, a*x^n:

evalAt :: (Num a, Integral n) => a -> Poly a n -> a
evalAt x = M.foldrWithKey (\n a b -> b + a*x^n) 0 . coeffMap

If we want to use a Map function, we can lift it from Map n a to Poly n a.
I'd like to be able to map on the coefficients, but I don't want to make this an instance of Functor because it's a classic student error to apply operations like squaring, applying trigonometrical or logarithmic functions or taking square roots term by term, when in fact only a tiny few things like scalar multiplication, differentiation and integration work like this. Providing fmap encourages you to do wong things like fmap (+1) instead of (+ (constant 1)).

mapCoeffs :: (a -> b) -> Poly a n -> Poly b n
mapCoeffs f = lift (fmap f)

Maps already collect like terms automatically, but we'll want to omit terms with zero coefficients:

strikeZeros :: (Num a,Eq a) => Poly a n -> Poly a n
strikeZeros =  lift $  M.filter (/= 0)                      

Now we can make the instances:

instance (Eq a,Num a,Ord n,Num n) => Eq (Poly a n) where
   f == g = f - g == zero

instance (Eq a,Num a,Num n,Ord n) => Num (Poly a n) where
   fromInteger = constant . fromInteger
   signum (Poly m) | M.null m = zero
                   | otherwise = let (n,a) = M.findMax m in 
                        Poly $ M.singleton n (signum a)
   abs =  mapCoeffs abs
   negate = mapCoeffs negate
   (+) = (strikeZeros.) . (Poly.) . ((M.unionWith (+)) `on` coeffMap)
   (Poly m) * (Poly m') = Poly $ 
          M.fromListWith (+) [(n+n',a*a') | (n,a)<-M.assocs m, (n',a')<-M.assocs m']

In action:

ghci> 3*x^4 + 6 + 2*x^7
Poly {coeffMap = fromList [(0,6),(4,3),(7,2)]}