Jikka.Core.Convert.MakeScanl

\[ \newcommand\int{\mathbf{int}} \newcommand\bool{\mathbf{bool}} \newcommand\list{\mathbf{list}} \]

Documentation

run :: (MonadAlpha m, MonadError Error m) => Program -> m Program

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\)

internal rules

rule :: MonadAlpha m => RewriteRule m

reduceScanlBuild :: Monad m => RewriteRule m

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)\)

reduceFoldlSetAtRecurrence :: MonadAlpha m => RewriteRule m

• 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).

reduceFoldlSetAtAccumulation :: MonadAlpha m => RewriteRule m

• 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).

reduceFoldlSetAtGeneric :: MonadAlpha m => RewriteRule m

getRecurrenceFormulaBase :: Expr -> ([Expr], Expr)

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

getRecurrenceFormulaStep1 :: MonadAlpha m => Integer -> Type -> VarName -> VarName -> Expr -> m (Maybe Expr)

getRecurrenceFormulaStep1 removes At in body.

getRecurrenceFormulaStep :: MonadAlpha m => Integer -> Integer -> Type -> VarName -> VarName -> Expr -> m (Maybe Expr)

getRecurrenceFormulaStep replaces At in body with Proj.