Skip to content

Invert case expressions #341

@julianhyde

Description

@julianhyde

Extend predicate inversion (introduced in #217) to handle case expressions with multiple arms, enabling queries like:

from x where (case x of 1 => true | 3 => true | _ => false);

> val it = [1, 3] : int bag

Currently this fails because the case expression cannot be inverted.

A more advanced example uses constructor patterns with predicates on the payloads.

from e where (case e of
    INL 0 => true
  | INL 6 => false
  | INR b => not b
  | INL 7 => true
  | INL 100 => true
  | INL n => n >= 5 andalso n <= 8);

> val it = [INL 0, INL 5, INL 7, INL 8, INR false, INL 100] : (int, bool) either bag

Note:

  • INL 7 appears only once even though two arms match it;
  • INL 6 does not appear, because it is excluded by INL 6 => false before reaching the branch INL n => n >= 5 andalso n <= 8 that would include it;
  • the INL n arm uses range inversion;
  • INR b => not b inverts to b = false (or just iterates over boolean, which is a practically finite type);
  • constant patterns like INL 0 use point inversion.

Proposed approach

Transform the multi-arm case into an orelse of singleton cases:

case x of p1 => e1 | p2 => e2 | _ => false

becomes:

(case x of p1 => e1 | _ => false) orelse (case x of p2 => e2 | _ => false)

The existing maybeUnion rule in Generators handles orelse by recursively inverting each branch and combining them via generateUnion. This avoids duplicating the upstream query.

Each singleton case then requires its own inversion:

  • Constant patterns (1 => true) reduce to equality (x = 1), handled by maybePoint
  • Constructor patterns (SOME n => e) generate the constructor shape and push e as a constraint on payload variables

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions