Advanced Collection Pattern Matching: Multiset, Set, and Nested Join Patterns with Bitmask Optimization

The practical expressiveness of non-linear pattern matching is insufficient with basic join patterns (`xs ++ ys`) alone; order-independent collection matching is indispensable. This paper reports on the design and implementation of multiset patterns (order-independent matching with duplicates), set patterns (order-independent matching with uniqueness constraints), nested join patterns (recursive list splitting), and logical connective patterns (And/Or/Not) in the egison-patterns library. The multiset matching employs a backtracking algorithm, and the optimized implementation adopts uint64 bitmask-based O(1) index tracking. For collections of 64 elements or fewer, the bitmask approach demonstrates significant improvements in cache efficiency compared to the HashSet approach. The integration of non-linear variables with collection patterns enables natural expression of patterns such as "detecting duplicate elements in a multiset."