refactor: conflict detection uses O(n²) elem on lists — switch to Set operations #26

New issue

Closed

opened 2026-06-10 14:48:22 +02:00 by yorunikakeru · 0 comments

yorunikakeru commented

2026-06-10 14:48:22 +02:00

Owner

Problem

Both intraConflict and conflictingName in DSL.Validate perform membership tests using elem on lists after nubOrd:

-- intraConflict (line 121)
conflicting = [name | name <- enabled, name `elem` disabled]  -- O(|enabled| × |disabled|)

-- conflictingName (lines 143–144)
[name | name <- enabledLeft, name `elem` disabledRight]       -- O(n²)
    <> [name | name <- disabledLeft, name `elem` enabledRight] -- O(n²)

nubOrd builds a Set internally to deduplicate but then returns a list, throwing away the Set. The subsequent elem rebuilds the membership cost from scratch.

Fix

Build Set Text once per action list and use Set.intersection / Set.member:

-- intraConflict
let enabledSet  = Set.fromList [name | ServiceAction (Service.Enable  (Service.ServiceName name)) <- actions]
    disabledSet = Set.fromList [name | ServiceAction (Service.Disable (Service.ServiceName name)) <- actions]
    conflicting = Set.toList (Set.intersection enabledSet disabledSet)

-- conflictingName
conflictingName left right =
    listToMaybe $ Set.toList $
        Set.intersection enabledLeft disabledRight
            <> Set.intersection disabledLeft enabledRight

Data.Set is already imported in DSL.Validate (used by duplicateName), so no new dependency is needed.

Note

The action-extraction pattern ([name | ServiceAction (Service.Enable (Service.ServiceName name)) <- actions]) is also duplicated 4× across intraConflict and conflictingName. Extracting helpers extractEnabled :: [Action] -> Set Text and extractDisabled :: [Action] -> Set Text would address both issues at once.

## Problem Both `intraConflict` and `conflictingName` in `DSL.Validate` perform membership tests using `elem` on lists after `nubOrd`: ```haskell -- intraConflict (line 121) conflicting = [name | name <- enabled, name `elem` disabled] -- O(|enabled| × |disabled|) -- conflictingName (lines 143–144) [name | name <- enabledLeft, name `elem` disabledRight] -- O(n²) <> [name | name <- disabledLeft, name `elem` enabledRight] -- O(n²) ``` `nubOrd` builds a `Set` internally to deduplicate but then returns a list, throwing away the `Set`. The subsequent `elem` rebuilds the membership cost from scratch. ## Fix Build `Set Text` once per action list and use `Set.intersection` / `Set.member`: ```haskell -- intraConflict let enabledSet = Set.fromList [name | ServiceAction (Service.Enable (Service.ServiceName name)) <- actions] disabledSet = Set.fromList [name | ServiceAction (Service.Disable (Service.ServiceName name)) <- actions] conflicting = Set.toList (Set.intersection enabledSet disabledSet) -- conflictingName conflictingName left right = listToMaybe $ Set.toList $ Set.intersection enabledLeft disabledRight <> Set.intersection disabledLeft enabledRight ``` `Data.Set` is already imported in `DSL.Validate` (used by `duplicateName`), so no new dependency is needed. ## Note The action-extraction pattern (`[name | ServiceAction (Service.Enable (Service.ServiceName name)) <- actions]`) is also duplicated 4× across `intraConflict` and `conflictingName`. Extracting helpers `extractEnabled :: [Action] -> Set Text` and `extractDisabled :: [Action] -> Set Text` would address both issues at once.

yorunikakeru referenced this issue from a commit

2026-06-12 18:11:35 +02:00

refactor(validate): use Set intersections for conflict detection

yorunikakeru referenced this issue from a pull request that will close it,

2026-06-12 18:13:32 +02:00

refactor/issue-26-set-conflict-detection #35

yorunikakeru closed this issue

2026-06-12 18:13:58 +02:00