Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
finding a derivative in haskell, first attempt
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'
@hdgarrood

This comment has been minimized.

Copy link
Owner Author

commented Aug 7, 2014

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.