Copyright | (c) Kimiyuki Onaka 2021 |
---|---|
License | Apache License 2.0 |
Maintainer | kimiyuki95@gmail.com |
Stability | experimental |
Portability | portable |
Safe Haskell | None |
Language | Haskell2010 |
Synopsis
- run :: (MonadAlpha m, MonadError Error m) => Program -> m Program
- rule :: (MonadAlpha m, MonadError Error m) => RewriteRule m
- runFunctionBody :: (MonadAlpha m, MonadError Error m) => VarName -> VarName -> VarName -> Expr -> VarName -> VarName -> VarName -> MaybeT m Expr
Documentation
run :: (MonadAlpha m, MonadError Error m) => Program -> m Program Source #
run
converts Kubaru DP
(for each \(i\), updates (
mathrm{dp}(j) gets f(mathrm{dp}(j), mathrm{dp}(i))
) for each \(j \gt i\))
to Morau DP
(for each \(i\), computes (
mathrm{dp}(i) = F(lbrace mathrm{dp}(j) mid j lt i rbrace)
)).
Examples
Before:
foldl (fun dp i -> foldl (fun dp j -> setAt dp j ( f dp[j] dp[i]) ) dp (range (i + 1) n) ) dp (range n)
After:
build (fun dp' -> foldl (fun dp_i j -> f dp_i dp'[j] ) dp[i] (range i) ) [] n
internal rules
rule :: (MonadAlpha m, MonadError Error m) => RewriteRule m Source #
TODO: remove the assumption that the length of a
is equals to n
runFunctionBody :: (MonadAlpha m, MonadError Error m) => VarName -> VarName -> VarName -> Expr -> VarName -> VarName -> VarName -> MaybeT m Expr Source #
runFunctionBody c i j step y x k
returns step'(y, x, i, k)
s.t. step(c, i, j) = step'(c[i + j + 1], c[i], i, i + j + 1)