RFC: Polymorphic Set Operations (intersect, difference, union)

[KrisSimon]

Problem Statement

Given two lists:

• A = [2, 3, 5]
• B = [1, 2, 3, 4]

We want to compute:

• Intersection: [2, 3] (elements in both)
• Difference A-B: [5] (elements in A but not B)
• Difference B-A: [1, 4] (elements in B but not A)

Currently, ARO has no built-in set operations. This RFC proposes adding them as polymorphic Compute operations that work across Lists, Strings, and nested Objects.

---

Design Goals

1. Polymorphic: Same operation works on different types
2. Consistent with ARO philosophy: Natural language syntax, happy path focus
3. Extensible: Plugins can add custom operations via ComputationService
4. Minimal new concepts: Leverage existing Compute action pattern

---

Proposed Syntax

(* Set operations - polymorphic by type *)
<Compute> the <common: intersect> from <list-a> with <list-b>.
<Compute> the <only-in-a: difference> from <list-a> with <list-b>.
<Compute> the <all: union> from <list-a> with <list-b>.

(* Works on strings - character-level *)
<Compute> the <shared: intersect> from "hello" with "bello".
(* Result: "ello" *)

(* Works on objects - deep recursive comparison *)
<Compute> the <common: intersect> from <obj-a> with <obj-b>.

---

Type Behavior Matrix

Operation	Lists	Strings	Objects (Deep)
intersect	Elements in both	Chars in both (order preserved)	Keys with matching values (recursive)
difference	In A, not in B	Chars in A, not in B	Keys/values in A, not in B
union	All unique elements	All unique chars	Merge keys (A wins conflicts)

---

Implementation Approaches Considered

We evaluated three approaches for adding set operations to ARO. Below is a detailed comparison with pros, cons, and our recommendation.

---

Approach 1: Compute Operations ✅ RECOMMENDED

Add intersect, difference, union as operations within the existing ComputeAction, following the polymorphic pattern already established for operations like length, uppercase, and hash.

Syntax:

<Compute> the <common: intersect> from <list-a> with <list-b>.
<Compute> the <only-in-a: difference> from <list-a> with <list-b>.
<Compute> the <all: union> from <list-a> with <list-b>.

Pros

Benefit	Explanation
Polymorphic by design	Same operation works on Lists, Strings, and Objects - just like length returns count for strings, arrays, and dicts
No new verbs	Users don't need to learn new action verbs; Compute is already familiar
Consistent with ARO-0035	Uses qualifier-as-name syntax (<result: operation>) already established
Plugin extensible	Plugins can add custom operations via ComputationService protocol - no ActionProtocol needed
Less code to maintain	Operations are methods in ComputeAction, not separate classes
Type-aware automatically	Runtime type checking (as?) handles different types elegantly
Fits ARO philosophy	Operations are transformations, not verbs - conceptually correct

Cons

Drawback	Mitigation
Two-operand operations new to Compute	from...with syntax already supported; just need implementation
Compute getting larger	Can refactor into helper module if needed
Less discoverable	Document in action reference alongside other Compute operations

---

Approach 2: New Actions (IntersectAction, DifferenceAction) ❌ NOT RECOMMENDED

Create dedicated ActionImplementation structs for each set operation.

Syntax:

<Intersect> the <common> from <list-a> with <list-b>.
<Difference> the <only-in-a> from <list-a> with <list-b>.
<Union> the <all> from <list-a> with <list-b>.

Pros

Benefit	Explanation
Explicit verbs	<Intersect> is immediately clear what it does
Specialized validation	Each action can validate its specific requirements
Separate concerns	Each operation is its own class

Cons

Drawback	Why It Matters
Adds 3 new verbs	ARO already has 50+ verbs; adding more increases learning curve
Inconsistent pattern	Other transformations (length, uppercase) are Compute ops, not separate actions
More code	3 new files, 3 new registrations, 3x maintenance
Plugin complexity	Plugins must implement full ActionImplementation protocol instead of simple ComputationService
Verb proliferation	Sets a precedent for more action verbs for each operation

Why Not Chosen

This approach treats set operations as verbs (things you do) rather than computations (transformations). In ARO's design philosophy:

• Actions = verbs that interact with the world (Extract, Store, Send, Return)
• Compute = transformations on data (length, hash, uppercase, intersect)

Set operations are clearly transformations, not world-interactions. Using Compute aligns with the language's conceptual model.

---

Approach 3: Filter with in/not in Operators ⚠️ PARTIAL SOLUTION

Enhance the existing Filter action to support array membership testing.

Current limitation:

(* Only works with CSV strings, not arrays *)
<Filter> the <x> from <items> where <v> in "1,2,3,4".

Proposed enhancement:

(* Accept arrays for membership testing *)
<Filter> the <included> from <items> where <value> in <list-b>.
<Filter> the <excluded> from <items> where <value> not in <list-b>.

Pros

Benefit	Explanation
Uses existing action	No new verbs or operations
Intuitive for filtering	where <field> in <list> reads naturally
not in is useful	Missing operator that should be added regardless

Cons

Drawback	Why It's Limiting
Object arrays only	Filter needs field access; can't work on [2, 3, 5] directly
Requires wrapping	Must use [{v: 2}, {v: 3}] instead of [2, 3]
No string support	Can't intersect strings like "hello" and "bello"
No deep objects	Can't recursively compare nested structures
Not a transformation	Filter selects from one list; doesn't compute intersection of two

Verdict

Useful enhancement, but NOT a complete solution. We should add not in and array support to Filter regardless, but this doesn't replace the need for proper set operations in Compute.

---

Comparison Summary

Criteria	Compute Ops	New Actions	Filter Enhancement
Polymorphic (Lists, Strings, Objects)	✅ Yes	✅ Yes	❌ Objects only
Deep recursive comparison	✅ Yes	✅ Yes	❌ No
No new verbs	✅ Yes	❌ No (+3 verbs)	✅ Yes
Plugin extensible	✅ Simple	⚠️ Complex	N/A
Consistent with ARO patterns	✅ Yes	❌ No	✅ Yes
Works on primitives	✅ Yes	✅ Yes	❌ No
Implementation effort	Low	Medium	Low

---

Final Decision: Compute Operations + Filter Enhancement

We recommend:

1. Primary solution: Add intersect, difference, union as Compute operations
2. Secondary enhancement: Add not in operator and array support to Filter

This provides:

• Full polymorphic set operations via Compute
• Membership filtering via Filter for object arrays
• Minimal new concepts to learn
• Plugin extensibility via existing protocols

---

Complete Example

(Application-Start: Set Operations Demo) {
    <Log> the <h> for the <console> with "=== Set Operations Demo ===".

    (* === LISTS === *)
    <Create> the <list-a> with [2, 3, 5].
    <Create> the <list-b> with [1, 2, 3, 4].

    <Compute> the <common: intersect> from <list-a> with <list-b>.
    <Log> the <r> for the <console> with "Intersection:".
    <Log> the <r> for the <console> with <common>.
    (* Output: [2, 3] *)

    <Compute> the <only-a: difference> from <list-a> with <list-b>.
    <Log> the <r> for the <console> with "A - B:".
    <Log> the <r> for the <console> with <only-a>.
    (* Output: [5] *)

    <Compute> the <only-b: difference> from <list-b> with <list-a>.
    <Log> the <r> for the <console> with "B - A:".
    <Log> the <r> for the <console> with <only-b>.
    (* Output: [1, 4] *)

    <Compute> the <all: union> from <list-a> with <list-b>.
    <Log> the <r> for the <console> with "Union:".
    <Log> the <r> for the <console> with <all>.
    (* Output: [2, 3, 5, 1, 4] *)

    (* === STRINGS === *)
    <Compute> the <shared-chars: intersect> from "hello" with "bello".
    <Log> the <r> for the <console> with "String intersection:".
    <Log> the <r> for the <console> with <shared-chars>.
    (* Output: "ello" *)

    <Compute> the <unique-chars: difference> from "hello" with "bello".
    <Log> the <r> for the <console> with "String difference:".
    <Log> the <r> for the <console> with <unique-chars>.
    (* Output: "h" *)

    (* === DEEP OBJECTS === *)
    <Create> the <obj-a> with {
        name: "Alice",
        age: 30,
        address: {
            city: "NYC",
            zip: "10001"
        }
    }.
    <Create> the <obj-b> with {
        name: "Alice",
        age: 31,
        address: {
            city: "NYC",
            state: "NY"
        }
    }.

    <Compute> the <common-fields: intersect> from <obj-a> with <obj-b>.
    <Log> the <r> for the <console> with "Object intersection:".
    <Log> the <r> for the <console> with <common-fields>.
    (* Output: { name: "Alice", address: { city: "NYC" } } *)

    (* === FILTER WITH NOT IN === *)
    <Create> the <items> with [
        {id: 1, value: 2},
        {id: 2, value: 3},
        {id: 3, value: 5},
        {id: 4, value: 7}
    ].
    <Create> the <exclude-list> with [3, 5].

    <Filter> the <included> from <items> where <value> in <exclude-list>.
    <Log> the <r> for the <console> with "Items in exclude-list:".
    <Log> the <r> for the <console> with <included>.
    (* Output: [{id: 2, value: 3}, {id: 3, value: 5}] *)

    <Filter> the <excluded> from <items> where <value> not in <exclude-list>.
    <Log> the <r> for the <console> with "Items NOT in exclude-list:".
    <Log> the <r> for the <console> with <excluded>.
    (* Output: [{id: 1, value: 2}, {id: 4, value: 7}] *)

    <Return> an <OK: status> for the <demo>.
}

---

Plugin Extensibility

The existing ComputationService protocol allows plugins to add custom set operations:

public struct CustomSetOperations: ComputationService {
    public func compute(named: String, input: Any) async throws -> any Sendable {
        switch named {
        case "symmetric-difference":
            // A XOR B = (A - B) ∪ (B - A)
            guard let (a, b) = input as? ([any Sendable], [any Sendable]) else {
                throw ActionError.typeMismatch(...)
            }
            let aMinusB = difference(a, b)
            let bMinusA = difference(b, a)
            return union(aMinusB, bMinusA)
        default:
            throw ActionError.unknownOperation(named)
        }
    }
}

// Register at startup
context.register(CustomSetOperations())

No architecture changes needed - the design is already extensible.

---

Files to Modify

File	Changes
Sources/ARORuntime/Actions/BuiltIn/ComputeAction.swift	Add intersect/difference/union with polymorphic dispatch
Sources/ARORuntime/Actions/BuiltIn/QueryActions.swift	Add not in operator, make in accept arrays

Files to Create

File	Purpose
Examples/SetOperations/main.aro	Demo showing all operations

---

Questions for Discussion

1. Should union deduplicate by default, or preserve duplicates?
2. For string operations, should we preserve character order from the first string or sort alphabetically?
3. Should we add a symmetric-difference built-in, or leave it to plugins?
4. Any edge cases we should consider for deep object comparison?

---

Feedback welcome!

[KrisSimon]

1. union should deduplicate by default
2. For string operations, preserve character order
3. leave symmetric-difference to plugins, create another example for it
4. Think about edge-cases and discuss it here before we accept this as an issue. @claude

[KrisSimon]

Thanks for the decisions! Here's my analysis of edge cases we should consider:

Edge Cases for Deep Object Comparison

1. Type Mismatches at Same Key

<Create> the <a> with { value: 42 }.
<Create> the <b> with { value: "42" }.
<Compute> the <result: intersect> from <a> with <b>.
(* Result: {} or { value: 42 }? *)

Recommendation: Empty result {} - strict type equality. 42 !== "42".

2. Null vs Missing Keys

<Create> the <a> with { name: "Alice", age: null }.
<Create> the <b> with { name: "Alice" }.
<Compute> the <result: intersect> from <a> with <b>.
(* Is { age: null } included? *)

Recommendation: { name: "Alice" } only. null in A with missing key in B = no match.

3. Empty Arrays/Objects

<Create> the <a> with { items: [] }.
<Create> the <b> with { items: [] }.
<Compute> the <result: intersect> from <a> with <b>.
(* Include { items: [] }? *)

Recommendation: Yes, include { items: [] }. Empty arrays are equal.

4. Array Order Sensitivity

<Create> the <a> with { tags: ["a", "b"] }.
<Create> the <b> with { tags: ["b", "a"] }.
<Compute> the <result: intersect> from <a> with <b>.

Recommendation: { tags: ["a", "b"] } - arrays within objects use set intersection (order-independent), not positional comparison.

5. Circular References

(* If ARO ever supports circular structures *)
<Create> the <a> with { self: <a> }.

Recommendation: Detect cycles and throw error. Deep recursion with cycles = infinite loop.

6. Very Deep Nesting

<Create> the <a> with { l1: { l2: { l3: { l4: { l5: { value: 1 } } } } } }.

Recommendation: No arbitrary depth limit. Trust the runtime. If stack overflows, it's a user problem.

---

Edge Cases for Strings

7. Unicode and Grapheme Clusters

<Compute> the <result: intersect> from "café" with "cafe".
(* Is 'é' (e + combining accent) equal to 'é' (single char)? *)

Recommendation: Use Swift's native Character comparison (grapheme clusters). "é" as single char matches "é" as composed.

8. Case Sensitivity

<Compute> the <result: intersect> from "Hello" with "hello".
(* Result: "ello" or "Hello"? *)

Recommendation: Case-sensitive by default. "H" !== "h". Result: "ello".

9. Empty String

<Compute> the <result: intersect> from "hello" with "".

Recommendation: Result is "". Intersection with empty set is empty.

---

Edge Cases for Lists

10. Duplicate Elements

<Create> the <a> with [1, 2, 2, 3].
<Create> the <b> with [2, 2, 2, 4].
<Compute> the <result: intersect> from <a> with <b>.
(* Result: [2] or [2, 2]? *)

Recommendation: [2, 2] - preserve duplicates up to the minimum count in both lists. This matches mathematical multiset intersection.

Alternative: [2] - treat as sets (deduplicate). Simpler but loses information.

This is the most important edge case to decide.

11. Mixed Types in Lists

<Create> the <a> with [1, "1", true].
<Create> the <b> with [1, "1", 1].
<Compute> the <result: intersect> from <a> with <b>.

Recommendation: [1, "1"] - strict type equality. true !== 1.

12. Nested Objects in Lists

<Create> the <a> with [{ id: 1, name: "Alice" }, { id: 2, name: "Bob" }].
<Create> the <b> with [{ id: 1, name: "Alice" }, { id: 3, name: "Charlie" }].
<Compute> the <result: intersect> from <a> with <b>.

Recommendation: [{ id: 1, name: "Alice" }] - deep equality for objects in lists.

---

Summary of Recommendations

Edge Case	Recommendation
Type mismatch at key	No match (strict equality)
null vs missing	No match
Empty arrays/objects	Equal (include in result)
Array order in objects	Order-independent (set intersection)
Circular references	Throw error
Deep nesting	No limit
Unicode	Grapheme cluster comparison
Case sensitivity	Case-sensitive
Empty string/list	Empty result
Duplicates in lists	TBD - need decision
Mixed types in lists	Strict type equality
Nested objects in lists	Deep equality

---

Open Question: Duplicates

The duplicate handling (edge case #10) is the most significant design decision remaining:

Option A: Set semantics (deduplicate)

• [1, 2, 2, 3] ∩ [2, 2, 4] = [2]
• Simpler, matches union deduplication behavior
• Loses information about frequency

Option B: Multiset semantics (preserve duplicates)

• [1, 2, 2, 3] ∩ [2, 2, 4] = [2, 2]
• More powerful, preserves information
• Inconsistent with union if union deduplicates

My recommendation: Option A (set semantics) for consistency with the decision that union deduplicates. All three operations should treat lists as sets.

What do you think?

[KrisSimon]

10. Duplicate Elements

<Create> the <a> with [1, 2, 2, 3].
<Create> the <b> with [2, 2, 2, 4].
<Compute> the <result: intersect> from <a> with <b>.
(* Result: [2, 2] *)

This is option B

[KrisSimon]

Proposal & Issue Created

Based on our discussion, I've created:

Proposal

ARO-0042: Polymorphic Set Operations

The proposal incorporates all decisions from this discussion:

• ✅ Compute operations (not new actions)
• ✅ Union deduplicates by default
• ✅ String operations preserve character order
• ✅ Symmetric-difference left to plugins
• ✅ Multiset semantics for list duplicates (Option B)
• ✅ All 12 edge cases documented

Implementation Tracking

Issue: #98

Feature Branch

Branch: feature/aro-0042-set-operations

---

Ready for implementation when approved. No PR created yet per request.