run reduces summations and products.

• This doen't do nothing about Foldl.

Examples

Before:

foldl (fun y x -> y + x) 0 (range n)

After:

x * (x - 1) / 2

List of builtin functions which are reduced

Target functions

• Sum \(: \list(\int) \to \int\)
• Product \(: \list(\int) \to \int\)
• ModSum \(: \list(\int) \to \int \to \int\)
• ModProduct \(: \list(\int) \to \int \to \int\)

Arithmetical functions

• Negate \(: \int \to \int\)
• Plus \(: \int \to \int \to \int\)
• Minus \(: \int \to \int \to \int\)
• Mult \(: \int \to \int \to \int\)
• Pow \(: \int \to \int \to \int\)

Arithmetical functions with modulo

• ModNegate \(: \int \to \int \to \int\)
• ModPlus \(: \int \to \int \to \int \to \int\)
• ModMinus \(: \int \to \int \to \int \to \int\)
• ModMult \(: \int \to \int \to \int \to \int\)
• ModPow \(: \int \to \int \to \int \to \int\)

List Build functions

• Nil \(: \forall \alpha. \list(\alpha)\)
• Cons \(: \forall \alpha. \alpha \to \list(\alpha) \to \list(\alpha)\)
• Range1 \(: \int \to \list(\int)\)

List Map functions

• Map \(: \forall \alpha \beta. (\alpha \to \beta) \to \list(\alpha) \to \list(\beta)\)
• Filter \(: \forall \alpha \beta. (\alpha \to \bool) \to \list(\alpha) \to \list(\beta)\)
• Reversed \(: \forall \alpha. \list(\alpha) \to \list(\alpha)\)
• Sorted \(: \forall \alpha. \list(\alpha) \to \list(\alpha)\)

TODO: implement this.

• This assumes that ModFloor is already propagated.

TODO: implement this.