Opened 4 years ago

Closed 4 years ago

Last modified 4 years ago

#10837 closed task (fixed)

Constant-time indexing of closed type family axioms

Reported by: jstolarek Owned by:
Priority: low Milestone: 8.0.1
Component: Compiler Version: 7.11
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s): Phab:D1261
Wiki Page:


Right now CoAxiom stores a list of CoAxBranches in a BranchList. But it would be useful to actually have a constant-time indexing into axioms. One code fragment when I really wanted to have this feature is in TcValidity.checkValidCoAxiom:

-- Replace n-th element in the list. Assumes 0-based indexing.
replace_br :: [CoAxBranch] -> Int -> CoAxBranch -> [CoAxBranch]
replace_br brs n br = take n brs ++ [br] ++ drop (n+1) brs

I believe this code could be rewritten in a much more efficient way using constant-time indexing.

The new data structure should most likely have a type that indicates whether the axiom is branched or not.

Change History (4)

comment:1 Changed 4 years ago by goldfire

Differential Rev(s): Phab:D1261
Status: newpatch

comment:2 Changed 4 years ago by Richard Eisenberg <eir@…>

In cd2840a/ghc:

Refactor BranchLists.

Now we use Array to store branches. This makes sense because we often
have to do random access (once inference is done). This also vastly
simplifies the awkward BranchList type.

This fixes #10837 and updates submodule utils/haddock.

comment:3 Changed 4 years ago by goldfire

Resolution: fixed
Status: patchclosed

No need for a test case. Do not merge.

comment:4 Changed 4 years ago by thomie

Milestone: 8.0.1
Note: See TracTickets for help on using tickets.