Opened 2 years ago

Closed 2 years ago

#13823 closed task (fixed)

Use NonEmpty lists in more places in the GHC API

Reported by: RyanGlScott Owned by: RyanGlScott
Priority: normal Milestone: 8.4.1
Component: Compiler Version: 8.3
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: #8782 Differential Rev(s): Phab:D3823
Wiki Page:


After GHC 8.2 is released and we drop support for building GHC with 7.10, we should try to use Data.List.NonEmpty in more places in the GHC API. I ran into this issue recently when using some functions from ListSetOps:

removeDups :: (a -> a -> Ordering) -> [a] -> ([a], [[a]]) 
findDupsEq :: (a -> a -> Bool) -> [a] -> [[a]]
equivClasses :: (a -> a -> Ordering) -> [a] -> [[a]] 

These type signatures are terrible. Really, they should be:

removeDups :: (a -> a -> Ordering) -> [a] -> ([a], [NonEmpty a]) 
findDupsEq :: (a -> a -> Bool) -> [a] -> [NonEmpty a]
equivClasses :: (a -> a -> Ordering) -> [a] -> [NonEmpty a] 

Since 90% of the time, the first thing you do after finding duplicates is to take a representative from the duplicate set. With lists, this requires the partial operation head, but with NonEmpty, this can be total like it was intended to be.

I'm sure there are other places in the API that could benefit from NonEmpty, so if you have any suggestions, please leave them here.

Change History (6)

comment:1 Changed 2 years ago by RyanGlScott

Owner: set to RyanGlScott

comment:2 Changed 2 years ago by mpickering

I've never found using NonEmpty to be worthwhile with Haskell's type system and in general I think we should be looking to remove ListSetOps rather than spending time making the API better.

comment:3 Changed 2 years ago by RyanGlScott

Well, I'm looking to avoid partially retrieving the representative of a list of duplicates, by hook or by crook. Do you have an idea in mind for a better ListSetOps replacement?

comment:4 Changed 2 years ago by RyanGlScott

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

comment:5 Changed 2 years ago by Ryan Scott <…>

In 7d69978/ghc:

Use NonEmpty lists to represent lists of duplicate elements

Three functions in `ListSetOps` which compute duplicate elements
represent lists of duplicates of `[a]`. This is a really bad way to go about
things, because these lists are guaranteed to always have at least one element
(the "representative" of the duplicates), and several places in the GHC API
call `head` (a partial function) on these lists of duplicates to retrieve the

This changes the representation of duplicates to `NonEmpty` lists instead,
which allow for many partial uses of `head` to be made total.

Fixes #13823.

Test Plan: ./validate

Reviewers: bgamari, austin, goldfire

Reviewed By: bgamari

Subscribers: goldfire, rwbarton, thomie

GHC Trac Issues: #13823

Differential Revision:

comment:6 Changed 2 years ago by RyanGlScott

Milestone: 8.4.1
Resolution: fixed
Status: patchclosed
Note: See TracTickets for help on using tickets.