Jikka.Core.Convert.SortAbs

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

Documentation

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

run reduces \(\lvert \sum _ {a_i \in a} \sum _ {a_j \in a} f(a, a_i, a_j) \rvert\) to \(\mathbf{let}~ b = \mathrm{sort}(a) ~\mathbf{in}~ \sum \sum f'(a, a_i, a_j)\) when \(f\) contains \(\lvert a_i - a_j \rvert\) and \(f(a, a_i, a_j) = f(a, a_j, a_i)\) holds.

Example

Before:

sum (map (fun (a_i: int) ->
    sum (map (fun (a_j: int) ->
        abs (a_i - a_j)
    ) a)
) a)

After:

let b = sort a
in sum (map (fun (i: int) ->
    (sum (map (fun (b_j: int) ->
        b_i - b_j
    ) b[:i])
    + 0
    + sum (map (fun (b_j: int) ->
        b_j - b_i
    ) b[i + 1:]))
) (range (length b)))

internal rules

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