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)]}

Answer 2

Here's an alternative solution to the other one I posted.

You seem to want to make an ADT for polynomials, where I'd use a Map, but let's go with a list of terms. First some imports:

import Data.Function (on)
import Data.List (sortBy, groupBy, foldl1')

This way a polynomial is a list of terms, sorted with the highest power first, and a term is aX^n, represented by X a n

newtype Poly a n = Poly {terms :: [Term a n]} deriving (Show)
data Term a n = X {coeff :: a, power :: n}  deriving (Eq,Show)

Let's make some simple polynomials:

zero = Poly []
x = Poly [X 1 1]

constant :: (Num a,Eq a,Num n) => a -> Poly a n
constant 0 = zero
constant a = Poly [X a 0]

Once we've defined the Num instance, we'll be able to make X 3 4 by writing 3*x^4.

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

subst :: (Num a, Integral n) => a -> Term a n -> a
subst x (X a n) = a * x ^ n

evalAt :: (Num a, Integral n) => a -> Poly a n -> a
evalAt x = sum . map (subst x) . terms

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 = Poly . map f' . terms
  where f' (X a n) = X (f a) n

We'll need to add and multiply terms, and collect like terms. When we collect like terms, we sort in reverse order of power and omit terms with zero coefficients.

addTerm (X a n) (X b m) | n == m = X (a+b) n
                        | otherwise = error "addTerm: mismatched powers" 
multTerm (X a n) (X b m) = X (a*b) (n+m)

collectLikeTerms :: (Num a, Ord n, Eq a) => Poly a n -> Poly a n
collectLikeTerms =  Poly . filter ((/= 0).coeff)            -- no zero coeffs
                         . map (foldl1' addTerm)            -- add the like powers
                         . groupBy ((==) `on` power)        -- group the like powers
                         . sortBy (flip compare `on` power) -- sort in reverse powers
                         . terms                            

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 []) = zero
   signum (Poly (t:_)) = constant . signum . coeff $ t
   abs =  mapCoeffs abs
   negate = mapCoeffs negate
   (+) = (collectLikeTerms.) . (Poly.) . ((++) `on` terms)
   (Poly ts) * (Poly ts') = collectLikeTerms $ Poly [multTerm t t' | t<-ts, t'<-ts']

In action:

ghci> 5*x^2 + 6*x^7 + 2
Poly {terms = [X {coeff = 6, power = 7},X {coeff = 5, power = 2},X {coeff = 2, power = 0}]}