Jikka-5.6.0.0: A transpiler from Python to C++ for competitive programming
Copyright(c) Kimiyuki Onaka 2021
LicenseApache License 2.0
Maintainerkimiyuki95@gmail.com
Stabilityexperimental
Portabilityportable
Safe HaskellNone
LanguageHaskell2010

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] <- 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

reduceScanlBuild :: Monad m => RewriteRule m Source #

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 Source #

reduceFoldlSetAtAccumulation :: MonadAlpha m => RewriteRule m Source #

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

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