Consider creating OrderedMap type to preserve insertion order in toString functions

## ✅ 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>` - ❌ key-sorted order only
- **Constructors** uses `Map) 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` 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

Read Value.fs and Type.fs to understand the current Map-based ordering, then review morphir-elm-ordering-analysis.md and map-determinism-analysis.md. The issue is marked resolved and only proposes OrderedMap for a future requirement; completion would require a decided insertion-order requirement and an agreed API.

Written by the indexing model from the issue text.