IntersectMBO / IntersectMBO/ouroboros-consensus

Introduce an abstraction for enumerations with a semantically important `Ord` instance

Open
#549 0 comments 1 reaction 0 assignees View on GitHub
Dominant language
Haskell
Stars
67
Forks
43
Avg merge
5d 13h
Merged PRs (30d)
43

Description

Often, the `stock`-derived `Ord` instance of a data type has no semantic meaning (i.e. it is just used to put them into `Set`s/`Map`s). In particular, one usually does not spend much thought on the order of constructors, even though it influences the derived `Ord` instance.

Hence, when the `Ord` instance *does* carry important semantic meaning (see https://github.com/input-output-hk/ouroboros-network/pull/3856#discussion_r1010978657 for an example), it would be nice to have a way to be very explicit about the ordering (that goes futher than a warning in the comments); in order to nudge someone modifying the data type in the future towards thinking about the implications for the `Ord` instance.

Ideally, this abstraction

1. statically guarantees lawful instances,
2. and has performance equal to handwritten code.

---

One possible approach might look like this: Instead of `stock`-deriving `Ord`/`Enum`/`Bounded` for a type `Foo`, the user implements
```haskell
class FromEnum a where
fromEnum_ :: a -> Int
```
for it, and uses the newtype `OrdFromEnum`
```haskell
newtype OrdFromEnum a = OrdFromEnum a

instance (FromEnum a, ...) => Ord a where
compare = comparing fromEnum

instance (FromEnum a, ...) => Enum a where
fromEnum = fromEnum_
toEnum = ...

instance (...) => Bounded a where ...
```
(probably using `GHC.Generic`s and an `Array` for `toEnum` for implementation) to allow users to write code such as
```haskell
data Foo = A | B | C
deriving stock (Eq, Show, Generic)
deriving (Ord, Enum, Bounded) via OrdFromEnum Foo

instance FromEnum a where
fromEnum_ = \case
A -> 1
B -> 2
C -> 3
```
For lawfulness, it additionally requires a test that `fromEnum_` is injective.

Note that this construction could also be split into two independent but composable parts (deriving `fromEnum` from `toEnum` or vice versa, and deriving `Ord` via `fromEnum`).

Other options include using a symmetric `ToEnum`-based approach or ordinary TH.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.