Assignment 2: Symbolic Differentiation

In this assignment you will implement a program that works with the symbolic data domain of algebraic expressions. Algebraic expressions are mathematical expressions involving variables, numeric constants, addition, subtraction, multiplication and exponentiation. You may carry out this assignment in groups of at most 3 students, with the number of items required to complete dependent on group size.

All students working in groups or alone, must implement both a symbolic derivative program and an algebraic simplification program. Students working in groups of 2 must also develop an unparser, while students working in groups of 3 must develop a parser for algebraic expressions as well.

Grammar for Algebraic Expressions

Consider the following grammar for algebraic expressions.

<expression> ::= <signed-term> | <expression> "+" <term> | <expression> "-" <term>
<signed-term> ::= "-" <term> | <term>
<term> ::= <factor> | <term> * <factor> 
<factor> ::= <element> | <element> ** <numeral>
<element> ::= <variable> | <numeral> | "(" <expression> ")"
<variable> ::= [a-z]
<numeral> ::= [0-9]+

Sample algebraic expressions include the following.

• -2 * x ** 3 + 4 * x + 7 representing \(-2x^3 + 4x + 7\)
• x * y * z ** 2 representing \(xyz^2\)

Haskell Representation of Algebraic Expressions

We will work with the following Haskell algebraic data type to represent algebraic expressions internally.

data ME = Num Int 
          | Var Char
          | Group ME
          | Add ME ME
          | Sub ME ME
          | Mul ME ME
          | Power ME Int
          | Neg ME
          deriving (Show, Ord, Eq)

Symbolic Differentiation Problem

The symbolic differentiation problem is to compute the derivative of a given algebraic expression with respect to a variable, according to the following rules.

• \(\frac{dn}{dx} = 0\) where \(n\) is a numeral and \(x\) is a variable.
• \(\frac{dx}{dx} = 1\)
• \(\frac{dy}{dx} = 0\) when \(y\) is a variable different from \(x\)
• \(\frac{d}{dx} (-f) = - \frac{df}{dx} \)
• \(\frac{d}{dx} (f + g) = \frac{df}{dx} + \frac{dg}{dx}\)
• \(\frac{d}{dx} (f \times g) = g\frac{df}{dx} + f\frac{dg}{dx}\)

All students whether working in groups or alone, must implement a symbolic differentiator according to the above rules.

Students working in groups of 2 or 3 must also implement the following rule.

• \(\frac{d}{dx} power(f, n) = n \times power(f, n-1) (\frac{df}{dx}) \)

Algebraic Simplification Problem

The algebraic simplification problem is to systematic simplify an algebraic expression according to a set of simplification rules, so that the final result is in fully simplified form (no more instances of the simplification rules apply).

All students must implement a simplifier using the following rules, where \(m\) and \(n\) represent numerals and \(f\) and \(g\) represent arbitrary algebraic expressions. You must implement both the simplification rules and the canonical form rules.

Canonical Form Rules

• \(n + f = f + n\)
• \(f + n + g = f + g + n\)
• \(m - f = -f + m \)
• \(f \times n = n \times f\)
• \(f \times (g \times h) = (f \times g) \times h\)

Simplification Rules

• \(f + 0 = f\)
• \(m + n = k\), where \(k\) is the sum of \(m\) and \(n\)
• \(f + m + n = f + k\), where \(k\) is the sum of \(m\) and \(n\)
• \(0 - f = -f \)
• \(f - 0 = f\)
• \(f - m - n = f - k\), where \(k\) is the sum of \(m\) and \(n\)
• \(m - n = k\), where \(k\) is the difference \(m\) and \(n\)

• \(0 \times f = 0 \)
• \(1 \times f = f \)
• \(m \times n = k\), where \(k\) is the product of \(m\) and \(n\)
• \(m \times f + n \times f = k \times f\), where \(k\) is the sum of \(m\) and \(n\)

Students working in groups of 2 or 3 must also implement conversions to canonical form and simplifications according to the following rules.

Canonical Form Rules

• \(power(f, m) \times g = g \times power(f, m) \)

Simplification Rules

• \(power(f, 0) = 1 \)
• \(power(f, 1) = f \)
• \(power(m, n) = k\), where \(k\) is \(m\) to the power \(n\)
• \(power(f, m) \times power(f, n) = power(f, k) \) where \(k\) is the sum of \(m\) and \(n\)

Unparsing

Students working in groups of 2 or 3 must implement an unparser which is capable of transforming the Haskell representation of algebraic expressions into an equivalent textual form, according to the grammar given above.

Parsing

Students working in groups of 3 must implement a parser to convert algebraic expressions in the textual representation according to the grammar given above into the internal Haskell form.

Interface Requirements

• Place your implementations in a file named "assig2.hs".
• Include in your file a function deriv :: ME -> Char -> ME that performs differentiation of an algebraic expression with respect to a variable according to the rules above. It should return the computed expression without simplifications applied.
• Include in your file a function simplifyME :: ME -> ME that systematically simplifies algebraic expressions according to the rules required.
• If you are working in groups, include in your file a function unparseME :: ME -> [Char] which generates the string representation of a mathematical object in according with the grammar given above.
• If you are working in groups of 3, include in your file a function parseME :: [Char] -> Maybe ME which can parse any legal algebraic expression according to the grammar above, and generates the appropriate representation of the algebraic expression if successful, or Nothing otherwise.