finding a derivative in haskell, first attempt

Derivative.hs

module Derivative where

data Expr = X             -- variable
          | S Integer     -- scalar
          | Expr :+: Expr -- sum
          | Expr :*: Expr -- product
          | Expr :^: Integer  -- exponent
          deriving (Show, Eq)


derivative' :: Expr -> Expr
derivative' X = S 1
derivative' (S _) = S 0
derivative' (p :+: q) = derivative p :+: derivative q
derivative' (p :*: q) = (derivative p :*: q) :+: (p :*: derivative q)
derivative' (p :^: i) = (S i :*: (p :^: (i - 1))) :*: derivative p

simplify :: Expr -> Expr
simplify (S 0 :*: _) = S 0
simplify (_ :*: S 0) = S 0
simplify (S 1 :*: p) = p
simplify (p :*: S 1) = p
simplify (S x :*: S y) = S (x * y)
simplify (S 0 :+: p) = p
simplify (p :+: S 0) = p
simplify (S x :+: S y) = S (x + y)
simplify (p :^: 0) = S 1 
simplify (p :^: 1) = p
simplify (p :+: q) = simplify p :+: simplify q
simplify (p :*: q) = simplify p :*: simplify q
simplify (p :^: q) = simplify p :^: q
simplify p = p

derivative :: Expr -> Expr
derivative = simplify . simplify . derivative'

In the declaration for Expr, the constructors are X, S (scalar), :+: (sum), :*: (product), and :^: (exponentiation) -- that is, you are allowed to have symbolic type constructors.

simplify is there because otherwise this happens:

>> derivative' (S 3 :*: ((X :^: 4) :+: X))
(S 0 :*: ((X :^: 4) :+: X)) :+: (S 3 :*: ((S 4 :*: (X :^: 3)) :+: S 1))

that is, d/dx (3 (x^4 + x)) = 0 * (x^4 + x) + 3 (4(x^3) + 1)
but really, having it in the form 12x^3 + 3 would be better.

simplify is a little gross, and so is the fact that I apply it twice. Possibly a better way to approach that issue would be to convert to some kind of normal form, probably involving a list of sums of lists of products, eliminate terms there, and then convert back to an Expr.