Jikka.Core.Convert.ConvexHullTrick

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

Documentation

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

run optimizes a DP which has the recurrence relation \[ \mathrm{dp}(i) = \min a(j) x(i) + b(j) \lbrace \mid j \lt i \rbrace + c(i) \] where only appropriate elements of \(\mathrm{dp}\) are used in \(a, x, b, c\).

internal rules

rule :: (MonadAlpha m, MonadError Error m) => RewriteRule m

parseLinearFunctionBody :: MonadAlpha m => VarName -> VarName -> Integer -> Expr -> m (Maybe (Expr, Expr, Expr, Expr, Expr))

parseLinearFunctionBody' :: VarName -> VarName -> VarName -> Expr -> Maybe (Expr, Expr, Expr, Expr)

parseLinearFunctionBody` parses the body of a linear function which can be decomposed to convex hull trick. parseLinearFunctionBody' f i j e finds a 4-tuple a, b, c, d where e = a(f[j], j) c(f[< i], i) + b(f[j], j) + d(f[< i], i).

TODO: What is the relation between j and k?