Problem
mkCase (Backend/IR.hs) builds decision trees by Jules Jacobs's algorithm and already prunes redundant tests through MatchHistory. Its column-selection heuristic, matchChosenByHeuristic (IR.hs:571), uses a single metric: pick the match present in the most other clauses. Maranget's composite pbaN ("Compiling Pattern Matching to Good Decision Trees") is sharper: p neededness (longest prefix of matching rows), b fewest distinct constructors (retire a column sooner), a fewest future sub-tests (look-ahead), N leftmost tie-break. On complex matches the composite produces smaller trees.
Approach
Replace the single-metric selection in matchChosenByHeuristic with the pbaN composite, scoring each candidate column on the four sub-metrics in order and breaking ties leftmost. The surrounding decision-tree construction and MatchHistory pruning are unchanged; this swaps only the column choice.
Prerequisites / Relations
Independent. Touches the same code as #184 (which extends MatchHistory to literal patterns and accumulates negative knowledge) but on an orthogonal axis: #184 is test pruning, this is column selection. They compose and neither blocks the other. A related trick, "leaf-as-function" (wrap a clause RHS shared across a wildcard fallthrough in a function to avoid duplicating its body), is worth a look only if a corpus survey shows pslua duplicates such bodies, noted as a possible follow-up, not part of this issue.
Verification / Measurement
A match whose column ordering makes pbaN and the current metric disagree compiles to a smaller tree (fewer tests) under the new heuristic, on a constructed multi-column case; eval goldens across the corpus stay unchanged, since only the tree shape moves, not the semantics. Code-size delta through #172.
Problem
mkCase(Backend/IR.hs) builds decision trees by Jules Jacobs's algorithm and already prunes redundant tests throughMatchHistory. Its column-selection heuristic,matchChosenByHeuristic(IR.hs:571), uses a single metric: pick the match present in the most other clauses. Maranget's compositepbaN("Compiling Pattern Matching to Good Decision Trees") is sharper:pneededness (longest prefix of matching rows),bfewest distinct constructors (retire a column sooner),afewest future sub-tests (look-ahead),Nleftmost tie-break. On complex matches the composite produces smaller trees.Approach
Replace the single-metric selection in
matchChosenByHeuristicwith thepbaNcomposite, scoring each candidate column on the four sub-metrics in order and breaking ties leftmost. The surrounding decision-tree construction andMatchHistorypruning are unchanged; this swaps only the column choice.Prerequisites / Relations
Independent. Touches the same code as #184 (which extends
MatchHistoryto literal patterns and accumulates negative knowledge) but on an orthogonal axis: #184 is test pruning, this is column selection. They compose and neither blocks the other. A related trick, "leaf-as-function" (wrap a clause RHS shared across a wildcard fallthrough in a function to avoid duplicating its body), is worth a look only if a corpus survey shows pslua duplicates such bodies, noted as a possible follow-up, not part of this issue.Verification / Measurement
A match whose column ordering makes
pbaNand the current metric disagree compiles to a smaller tree (fewer tests) under the new heuristic, on a constructed multi-column case; eval goldens across the corpus stay unchanged, since only the tree shape moves, not the semantics. Code-size delta through #172.