Copyright | (C) 2015, University of Twente |
---|---|

License | BSD2 (see the file LICENSE) |

Maintainer | Christiaan Baaij <christiaan.baaij@gmail.com> |

Safe Haskell | None |

Language | Haskell2010 |

# SOP: Sum-of-Products, sorta

The arithmetic operation for `Nat`

are, addition
(

), subtraction (`+`

), multiplication
(`-`

), and exponentiation (`*`

). This means we
cannot write expressions in a canonical SOP normal form. We can get rid of
subtraction by working with integers, and translating `^`

`a - b`

to `a + (-1)*b`

.
Exponentation cannot be getten rid of that way. So we define the following
grammar for our canonical SOP-like normal form of arithmetic expressions:

SOP ::= Product '+' SOP | Product Product ::= Symbol '*' Product | Symbol Symbol ::= Integer | Var | Var '^' Product | SOP '^' ProductE ProductE ::= SymbolE '*' ProductE | SymbolE SymbolE ::= Var | Var '^' Product | SOP '^' ProductE

So a valid SOP terms are:

x*y + y^2 (x+y)^(k*z)

, but,

(x*y)^2

is not, and should be:

x^2 * y^2

Exponents are thus not allowed to have products, so for example, the expression:

(x + 2)^(y + 2)

in valid SOP form is:

4*x*(2 + x)^y + 4*(2 + x)^y + (2 + x)^y*x^2

Also, exponents can only be integer values when the base is a variable. Although not enforced by the grammar, the exponentials are flatted as far as possible in SOP form. So:

(x^y)^z

is flattened to:

x^(y*z)

- data Symbol v c
- newtype Product v c = P {}
- newtype SOP v c = S {}
- reduceExp :: (Ord v, Ord c) => Symbol v c -> Symbol v c
- mergeS :: (Ord v, Ord c) => Symbol v c -> Symbol v c -> Either (Symbol v c) (Symbol v c)
- mergeP :: (Eq v, Eq c) => Product v c -> Product v c -> Either (Product v c) (Product v c)
- mergeSOPAdd :: (Ord v, Ord c) => SOP v c -> SOP v c -> SOP v c
- mergeSOPMul :: (Ord v, Ord c) => SOP v c -> SOP v c -> SOP v c
- normaliseExp :: (Ord v, Ord c) => SOP v c -> SOP v c -> SOP v c

# SOP types

(Eq v, Eq c) => Eq (Symbol v c) Source | |

(Ord v, Ord c) => Ord (Symbol v c) Source | |

(Outputable v, Outputable c) => Outputable (Symbol v c) Source |

(Eq v, Eq c) => Eq (Product v c) Source | |

(Ord v, Ord c) => Ord (Product v c) Source | |

(Outputable v, Outputable c) => Outputable (Product v c) Source |

(Eq v, Eq c) => Eq (SOP v c) Source | |

(Ord v, Ord c) => Ord (SOP v c) Source | |

(Outputable v, Outputable c) => Outputable (SOP v c) Source |

# Simplification

reduceExp :: (Ord v, Ord c) => Symbol v c -> Symbol v c Source

reduce exponentials

Performs the following rewrites:

x^0 ==> 1 0^x ==> 0 2^3 ==> 8 (k ^ i) ^ j ==> k ^ (i * j)

mergeS :: (Ord v, Ord c) => Symbol v c -> Symbol v c -> Either (Symbol v c) (Symbol v c) Source

Merge two symbols of a Product term

Performs the following rewrites:

8 * 7 ==> 56 1 * x ==> x x * 1 ==> x 0 * x ==> 0 x * 0 ==> 0 x * x^4 ==> x^5 x^4 * x ==> x^5 y*y ==> y^2

mergeP :: (Eq v, Eq c) => Product v c -> Product v c -> Either (Product v c) (Product v c) Source

Merge two products of a SOP term

Performs the following rewrites:

2xy + 3xy ==> 5xy 2xy + xy ==> 3xy xy + 2xy ==> 3xy xy + xy ==> 2xy

mergeSOPAdd :: (Ord v, Ord c) => SOP v c -> SOP v c -> SOP v c Source

Merge two SOP terms by additions