run replaces Foldl with Scanl.

Example

Before:

let xs = range n
xs[0] <- 0
xs[1] <- 1
foldl (fun a i -> do
   xs[i + 2] <- xs[i] + xs[i + 1]
   xs
) xs (range (n - 2))

After:

0 : map snd (
   scanl (fun a i -> (snd a, fst a + snd a))
         (0, 1)
         (range (n - 2)))

List of builtin functions which are reduced

Build functions

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

Map functions

• Scanl \(: \forall \alpha \beta. (\beta \to \alpha \to \beta) \to \beta \to \list(\alpha) \to \list(\beta)\)
• SetAt \(: \forall \alpha. \list(\alpha) \to \int \to \alpha \to \list(\alpha)\)

Fold functions

• Foldl \(: \forall \alpha \beta. (\beta \to \alpha \to \beta) \to \beta \to \list(\alpha) \to \beta\)
• At \(: \forall \alpha. \list(\alpha) \to \int \to \alpha\)

List of builtin functions which are reduced

• Nil \(: \forall \alpha. \list(\alpha)\)
• Cons \(: \forall \alpha. \alpha \to \list(\alpha) \to \list(\alpha)\)
• Scanl \(: \forall \alpha \beta. (\beta \to \alpha \to \beta) \to \beta \to \list(\alpha) \to \list(\beta)\)

• This assumes that Range2 and Range3 are already converted to Range1 (ShortCutFusion).
• This assumes that combinations Foldl and Map squashed (ShortCutFusion).
• This assumes that constants are already folded (ConstantFolding).

• This assumes that Range2 and Range3 are already converted to Range1 (ShortCutFusion).
• This assumes that combinations Foldl and Map squashed (ShortCutFusion).
• This assumes that constants are already folded (ConstantFolding).

getRecurrenceFormulaBase makes a pair ((a_0, ..., a_{k - 1}), a) from setat (... (setat a 0 a_0) ...) (k - 1) a_{k - 1}).

getRecurrenceFormulaStep1 removes At in body.

getRecurrenceFormulaStep replaces At in body with Proj.