Jikka.Core.Convert.KubaruToMorau

Documentation

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

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

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

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)