Jikka.Core.Convert.ShortCutFusion

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

Documentation

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

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

rule :: MonadAlpha m => RewriteRule m

reduceBuild :: MonadAlpha m => RewriteRule m

• Range1 remains.
• Range2 is removed.
• Range3 is removed.
• Nil and Cons are kept as is.

reduceMapBuild :: MonadAlpha m => RewriteRule m

reduceMap :: Monad m => RewriteRule m

reduceMapMap :: MonadAlpha m => RewriteRule m

• 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

reduceFoldMap :: MonadAlpha m => RewriteRule m

reduceFold :: Monad m => RewriteRule m

reduceFoldBuild :: MonadAlpha m => RewriteRule m