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.ShortCutFusion

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 does short cut fusion.

• This function is mainly for polymorphic reductions. This dosn't do much about concrete things, e.g., arithmetical operations.
• This doesn't do nothing about Scanl or SetAt.

## Example

Before:

length (map f (cons (-1) (range n)))

After:

n + 1

## 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)$$
• Range2 $$: \int \to \int \to \list(\int)$$
• Range3 $$: \int \to \int \to \int \to \list(\int)$$

### 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)$$

### Fold functions

• Foldl $$: \forall \alpha \beta. (\beta \to \alpha \to \beta) \to \beta \to \list(\alpha) \to \beta$$
• Len $$: \forall \alpha. \list(\alpha) \to \int$$
• At $$: \forall \alpha. \list(\alpha) \to \int \to \alpha$$
• Elem $$: \forall \alpha. \alpha \to \list(\alpha) \to \bool$$

# internal rules

• Range1 remains.
• Range2 is removed.
• Range3 is removed.
• Nil and Cons are kept as is.
• Functions are reordered as:
• Sort and Reversed (functions to reorder) are lastly applied to lists
• Map (functions to modify lists)
• Filter (funcitons to reduce lengths) is firstly applied to lists