Consider creating OrderedMap type to preserve insertion order in toString functions

[DamianReeves]

✅ Resolution

Status: Resolved - Removed redundant sorting code

We've removed the redundant List.sortBy fst calls from toString implementations in:

• Value.fs - Record case
• Type.fs - CustomTypeSpecification case
• Type.fs - CustomTypeDefinition case

Why this is safe:

• F# Map.toList already returns entries in key-sorted order (deterministic)
• The List.sortBy fst was redundant since Map.toList already provides sorted output
• Tests remain deterministic and all pass (190 tests passing)
• Behavior matches morphir-elm reference implementation (uses Dict.toList without additional sorting)

Key Insight: F# Map is implemented as a balanced binary tree sorted by key. Map.toList always returns entries in key-sorted order, regardless of insertion order. This makes the output deterministic, but it's key-sorted, not insertion-ordered.

When OrderedMap Would Be Needed

If we ever need to preserve insertion order while maintaining Map-like behavior, we would need to implement OrderedMap as proposed below. This would be necessary if:

1. Insertion order preservation becomes a requirement (e.g., for user-facing output, IR serialization, or roundtrip compatibility)
2. We want Map-like O(log n) lookups while preserving insertion order
3. We want to deviate from morphir-elm's key-sorted approach for insertion order preservation

Note: Currently, insertion order preservation is not a requirement - we match morphir-elm's key-sorted behavior, which is deterministic and sufficient for our use cases.

---

Original Problem

Currently, when converting IR structures to strings using toString functions, we're using F# Map which doesn't preserve insertion order. The Map.toList operation returns entries in key-sorted order, not insertion order. This affects:

1. Value.Record - Field ordering in record values
2. CustomTypeSpecification/Definition - Constructor ordering in type specifications

While we've added List.sortBy fst to ensure deterministic output, this means we're always outputting in alphabetical order rather than preserving the order fields/constructors were added.

Context

During implementation of toString functions for IR Value and Type elements, we discovered that:

• Type.Record uses List (Field<'attributes>) - ✅ preserves insertion order
• Value.Record uses Map<Name, Value<...>> - ❌ key-sorted order only
• Constructors uses Map<Name, (Name * Type<'attributes>) list> - ❌ key-sorted order only

morphir-elm Reference Implementation

After analyzing the morphir-elm reference implementation:

• Type.Record: Uses List (Field a) - preserves insertion order
• Value.Record: Uses Dict Name (Value ta va) - key-sorted order (uses Dict.toList without additional sorting)
• Constructors: Uses Dict Name (ConstructorArgs a) - key-sorted order

Key Finding: morphir-elm also uses Dict (key-sorted) for Value.Record and Constructors, so it doesn't preserve insertion order either.

Current Implementation

Our current F# implementation:

• Uses Map.toList - returns key-sorted entries (deterministic)
• Output is key-sorted (alphabetical by Name)
• Matches morphir-elm behavior

Options Considered

Option 1: Remove Redundant Sorting ✅ (Implemented)

• Action: Remove List.sortBy fst calls since Map.toList already returns sorted entries
• Impact: Output will be key-sorted (matching morphir-elm behavior)
• Breaking: No - just removes redundant code
• Result: Matches morphir-elm behavior exactly

Option 2: Change Data Structures to Lists (Breaking Change)

• Action: Change Map<Name, ...> to (Name * ...) list in IR model
• Impact: Preserves insertion order, but requires changes throughout codebase
• Breaking: Yes - changes IR model structure
• Result: Preserves insertion order, but doesn't match morphir-elm's Dict-based approach

Option 3: Create OrderedMap Wrapper (Future Consideration)

• Action: Create wrapper that tracks insertion order separately
• Impact: Preserves insertion order without changing IR model
• Breaking: No - but adds complexity
• Result: Preserves insertion order, but morphir-elm doesn't do this
• When needed: Only if insertion order preservation becomes a requirement

Proposed Solution: OrderedMap (For Future Use)

If insertion order preservation becomes a requirement, create an OrderedMap type that:

1. Maintains a list of keys in insertion order
2. Uses an internal Map for efficient lookups
3. Provides Map-like API for compatibility
4. Preserves insertion order when iterating

Implementation Sketch

```fsharp
namespace Morphir.IR

module OrderedMap =
type OrderedMap<'Key, 'Value when 'Key : comparison> =
private { Keys: 'Key list; Map: Map<'Key, 'Value> }

    static member Empty = { Keys = []; Map = Map.empty }
    
    member this.Add(key, value) =
        let newKeys = 
            if Map.containsKey key this.Map then 
                this.Keys  // Key exists, don't change order
            else 
                this.Keys @ [key]  // New key, append to end
        { Keys = newKeys; Map = this.Map.Add(key, value) }
    
    member this.ToList() = 
        this.Keys 
        |> List.map (fun k -> (k, this.Map.[k]))
    
    member this.ToMap() = this.Map
    
    member this.TryFind key = this.Map.TryFind key
    member this.ContainsKey key = Map.containsKey key this.Map
    // ... other Map-like operations

```

Questions to Consider (For Future)

1. Is insertion order preservation important?

   • For user-facing output (toString)?
   • For IR serialization/deserialization?
   • For roundtrip compatibility?

2. Should we deviate from morphir-elm?

   • morphir-elm uses Dict (key-sorted) - should we match this exactly?
   • Or is insertion order preservation a valuable enhancement?

3. Performance implications?

   • OrderedMap adds overhead (maintaining key list)
   • Is this acceptable for IR model operations?

4. Migration strategy?

   • How to migrate existing code using Map?
   • Should this be opt-in or default?

Related Work

• Issue: Implementation of toString functions for IR Value and Type elements
• Branch: feature/ir-modeling-work
• Analysis documents:
  • morphir-elm-ordering-analysis.md - morphir-elm behavior analysis
  • map-determinism-analysis.md - Map.toList determinism verification

References

• morphir-elm source: https://github.com/finos/morphir-elm
• Analysis documents: See morphir-elm-ordering-analysis.md and map-determinism-analysis.md in repository