Jikka-5.0.11.1: A transpiler from Python to C++ for competitive programming
Copyright (c) Kimiyuki Onaka 2021 Apache License 2.0 kimiyuki95@gmail.com experimental portable None Haskell2010

Jikka.Core.Convert.MakeScanl

Description

$\newcommand\int{\mathbf{int}} \newcommand\bool{\mathbf{bool}} \newcommand\list{\mathbf{list}}$

Synopsis

# Documentation

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

run replaces Foldl with Scanl.

## Example

Before:

let xs = range n
xs <- 0
xs <- 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

## 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 :: MonadAlpha m => Int -> Type -> VarName -> VarName -> Expr -> m (Maybe Expr) Source #

getRecurrenceFormulaStep1 removes At in body.

getRecurrenceFormulaStep :: MonadAlpha m => Int -> Int -> Type -> VarName -> VarName -> Expr -> m (Maybe Expr) Source #

getRecurrenceFormulaStep replaces At in body with Proj.