Haskell: better understanding algebraic data types
I am trying to build an algebraic data type that represents polynomials. Considering the definition that an integer constant is a polynomial and that if you add two polynomials or multiply two polynomials it will result in a polynomial.
I am having a hard time understanding how algebraic data types work in general and how I would go about doing it. I currently have
data Poly = Const Int |
Add Poly Poly |
Mult Poly Poly
However, I don't know what it even means or how to use it, I am just moving away from the examples I've seen in algebraic data types.
I have seen types like
data Tree = NullT |
Node Int Tree Tree
This makes more sense to me and how to use it. The polynomial example seems so abstract that 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 met an error
*Polynomial> evalPoly Poly 1
<interactive>:25:10: Not in scope: data constructor ‘Poly’
*Polynomial>
Edit again: Thanks for all your suggestions and help, it helped me create something that works for my purposes!
source to share
You seem to want to do an ADT for the polynomials, but I'd rather use a map. First imported:
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 simple simple polynomials be satisfied:
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
The standard polynomial thing is evaluating it with a specific value for x.
Here, the partially computed is b
added and added to the new member 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 the Map function, we can raise it from Map n a
to Poly n a
.
I would like to be able to match the coefficients, but I don't want to make it an instance of Functor, because it is a classic student mistake for applying operations like squaring, applying trigonometric or logarithmic functions, or using square roots in terms of when really only tiny things like scalar multiplication, differentiation and integration work like this. Providing fmap encourages you to do things like fmap (+1)
, not (+ (constant 1))
.
mapCoeffs :: (a -> b) -> Poly a n -> Poly b n
mapCoeffs f = lift (fmap f)
The cards are already collected as terms automatically, but we want to omit the terms with zero coefficients:
strikeZeros :: (Num a,Eq a) => Poly a n -> Poly a n
strikeZeros = lift $ M.filter (/= 0)
We can now make 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)]}
source to share
Here is an alternative solution for another that I wrote.
You seem to want to do an ADT for polynomials, where I would use a map, but let go of the list of terms. First imported:
import Data.Function (on)
import Data.List (sortBy, groupBy, foldl1')
So a polynomial is a list of terms sorted with the highest degree, and the aX ^ n term 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 simple simple polynomials be satisfied:
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 have defined an instance of Num, we can do X 3 4
it by writing 3*x^4
.
The standard polynomial thing is evaluating it with a specific 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 would like to be able to match the coefficients, but I don't want to make it an instance of Functor because it is a classic student mistake for applying operations like squaring, applying trigonometric or logarithmic functions, or taking square roots while in fact only tiny things like scalar multiplication, differentiation and integration work like this. Providing fmap encourages you to do things like fmap (+1)
, not (+ (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 will need to add and multiply terms and collect as terms. When we collect as terms, we sort in reverse order of cardinality and omit the 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
We can now make 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}]}
source to share