Add `Enum` instance to `Down`, flipping direction

[gergoerdi]

This is an idea that was prompted by my surprise that this behaviour is not already the case...

The ~Bounded and~ Enum instances of Data.Ord.Down should be changed such that

succ @(Down a) = fmap pred

and all other methods implemented similarly.

Implementation is in MR !8242.

[konsumlamm]

I'm not sure what Down you're looking at, but for the one in base (https://hackage.haskell.org/package/base-4.16.1.0/docs/Data-Ord.html#t:Down) the Bounded instance already works like that and there currently is no Enum instance.

[tomjaguarpaw]

Bounded was derived in 4.14 but this has since been changed.

[gergoerdi]

Bounded was derived in 4.14 but this has since been changed.

Ah, that's good to know -- I was looking at 8.10.7, and didn't expect this has changed since.

[tomjaguarpaw]

Surprisingly I can't find where this was discussed, although I remember reading the discussion.

[gergoerdi]

there currently is no Enum instance.

Looking at it in detail, the problem is that while enumFrom* could be implement with some smarts, toEnum/fromEnum would be tricky. Would it be acceptable to only have Enum (Down a) if not only Enum a, but also Bounded a? Because then, we could have

    fromEnum (Down x) = fromEnum (maxBound @a) - fromEnum x
    toEnum k = Down $ toEnum $ fromEnum (maxBound @a) - k

[tomjaguarpaw]

not only Enum a, but also Bounded a

and also Num a? And also some fairly strong compatibility condition between them (that really ought to hold but I don't know if it actually holds for instances in practice).

[tomjaguarpaw]

I guess the compatibility condition is that pred == subtract 1 and succ == (+ 1) so maybe not that strong.

[gergoerdi]

not only Enum a, but also Bounded a

and also Num a? And also some fairly strong compatibility condition between them (that really ought to hold but I don't know if it actually holds for instances in practice).

No, the subtraction is done on the Int side.

[tomjaguarpaw]

Ah so it is. That looks nice then!

[andreasabel]

@gergoerdi : Can you please change the issue title to reflect the updates?

[gergoerdi]

So I guess the actual implementation would look something like this:

instance (Enum a, Bounded a) => Enum (Down a) where
    succ = fmap pred
    pred = fmap succ

    fromEnum (Down x) = fromEnum (maxBound @a) - fromEnum x
    toEnum k = Down $ toEnum $ fromEnum (maxBound @a) - k

    enumFrom (Down x) = Down <$> enumFromThen x (pred x)
    enumFromTo (Down x) (Down y) = Down <$> enumFromThenTo x (pred x) y

[andreasabel]

there currently is no Enum instance.

@gergoerdi : So would the title rather be: Add Enum instance for Down ?

[gergoerdi]

Another approach that doesn't even require Bounded a, just flips the direction of succ/pred via negating fromEnum. Unfortunately, we still can't avoid also defining enumFrom and enumFromThen to ensure proper stopping:

instance (Enum a) => Enum (Down a) where
    fromEnum = negate . fromEnum . getDown
    toEnum = Down . toEnum . negate

    enumFrom (Down x) = Down <$> enumFromThen x (pred x)
    enumFromThen (Down x) (Down y) = map Down $ enumFromThen x y

TBH I don't know how kosher this is, because of the whole negate @Int minBound == minBound situation, but other than that corner case, it should work fine.

[Bodigrim]

Are there undesirable consequences of negate @Int minBound == minBound for instance Enum (Down Int) in particular?

[gergoerdi]

Are there undesirable consequences of negate @Int minBound == minBound for instance Enum (Down Int) in particular?

One thing I'm aware of is that if all we have is fromEnum/toEnum, then, while succ @Int fails, pred @(Down Int) quietly returns a wrong result:

λ» succ @Int maxBound
*** Exception: Prelude.Enum.succ{Int}: tried to take `succ' of maxBound
λ» pred @(Down Int) (Down maxBound)
Down {getDown = -9223372036854775808}

Of course, this is easily fixed by adding succ = fmap pred and pred = fmap succ as explicit method implementations.

[Bodigrim]

I think coerce is a better alternative to fmap.

[Bodigrim]

I like the proposal, but still feel a bit uneasy about it: it seems there is an unwritten assumption about connection between Enum, Bounded and Ord. Could it be spelled out? Are other existing instances in line with it?

[mixphix]

I'm not sure I support this proposal in its current form. Down has the explicit purpose of providing a simple wrapper with a flipped Ord instance. In this goal it excels. To add convoluted functionality to this class seems to diverge from its intent.

I would be more open to a new newtype (e.g. Descending) for this suggestion. Though Down a and Descending a would have the same Ord instance, the latter could require instance (Ord a, Enum a, Bounded a) => Ord (Descending a) so that its purpose is more clearly stated as being "the enumeration from the other direction" instead of "flipped comparison".

[gergoerdi]

I'm not sure I support this proposal in its current form. Down has the explicit purpose of providing a simple wrapper with a flipped Ord instance. In this goal it excels. To add convoluted functionality to this class seems to diverge from its intent.

FWIW, Down a already comes with a flipped Bounded instance, so this Enum instance merely extends that functionality. Also, with the version that goes via Int, we no longer have the Bounded a constraint on the proposed Enum (Down a) instance.

[Bodigrim]

@gergoerdi feel free to raise a GHC MR and trigger a vote.

[Bodigrim]

@gergoerdi just a gentle reminder that this awaits an action from your side.

[gergoerdi]

https://gitlab.haskell.org/ghc/ghc/-/merge_requests/8242

[monoidal]

Earlier discussion which resulted in removal of Enum (Down a): https://mail.haskell.org/pipermail/libraries/2020-September/030825.html

[Bodigrim]

@gergoerdi I left comments at https://gitlab.haskell.org/ghc/ghc/-/merge_requests/8242

[Bodigrim]

@gergoerdi what's the status of this?

[Bodigrim]

@gergoerdi unless there is a progress within two weeks, I'll close this as abandoned.

[sjoerdvisscher]

Shouldn't the instance for Bounded be changed to negate the bounds instead of swapping them? Otherwise the Enum and Bounded instances will be incompatible.

[tomjaguarpaw]

@sjoerdvisscher Can you give an example?

[sjoerdvisscher]

Sorry that made no sense. (I was somehow thinking Bounded was working with indices instead of actual values. No🤦posting🤦before🤦coffee!)

[gergoerdi]

@gergoerdi unless there is a progress within two weeks, I'll close this as abandoned.

I still think this is a good idea, but unfortunately the implementation is suffering from https://gitlab.haskell.org/ghc/ghc/-/merge_requests/8242#note_430441.

The problem there is that we can only implement enumFrom @(Down a) in terms of enumFromThen @a (since enumFrom @a "counts up", and we want to "count down"). The difference between the two is that enumFrom can look at the first element (the first argument) and decide upfront not to keep going, but enumFromTo must look at both arguments. And in the case of enumFrom (Down minBound) = coerce (enumFromThen minBound (pred minBound)), the second argument is bottom.

I don't have a solution to this :(

[Bodigrim]

@gergoerdi I think one solution is to add Bounded a constraint.

[Bodigrim]

@gergoerdi if you don't have a correct working patch to propose, I suggest we close this as withdrawn. What do you think?

[gergoerdi]

I'll try my hands at a Bounded-based implementation, it's just something I was hoping we can avoid...

On Sat, Sep 10, 2022, 22:21 ˌbodʲɪˈɡrʲim @.***> wrote:

@gergoerdi https://github.com/gergoerdi if you don't have a correct working patch to propose, I suggest we close this as withdrawn. What do you think?

— Reply to this email directly, view it on GitHub https://github.com/haskell/core-libraries-committee/issues/51#issuecomment-1242799333, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAA4KKIOPG2HRQAAZYA4PATV5TUUXANCNFSM5RYXMY5A . You are receiving this because you were mentioned.Message ID: @.***>

[Bodigrim]

@gergoerdi just a gentle reminder to make some progress, if you are still interested to champion this proposal. We are already past the initial deadline of two weeks.

[gergoerdi]

@gergoerdi just a gentle reminder to make some progress, if you are still interested to champion this proposal. We are already past the initial deadline of two weeks.

Well tbf there was ICFP in the meantime :)

Looking at it now, I don't see how Bounded a helps with the enumFrom vs. enumFromThen problem, so I guess this is ultimately not meant to be...

[Ericson2314]

I would take Enum out of base if it could. It has always felt like a lousy class to me. [x, ...] stuff can be done in a different way, I hope.

[sjoerdvisscher]

@gergoerdi Although ugly, this seems to work:

    enumFrom (Down x) =
      if fromEnum x == fromEnum (minBound :: a)
        then [Down x]
        else coerce $ enumFromThenTo x (pred x) minBound

Or am I missing something?

[gergoerdi]

Or am I missing something?

I've updated the MR based on this idea.

[Bodigrim]

Another opportunity is to require Eq a and check if x == minBound, which is probably slightly better than if fromEnum x == fromEnum (minBound :: a). E. g., imagine Int128 - it has instance Enum and instance Bounded, but fromEnum x == fromEnum (minBound :: a) results in too many false positives.

Dear CLC members, before we proceed to a vote, may I ask you to provide (non-binding) opinions on the proposal? @tomjaguarpaw @chessai @emilypi @cgibbard @mixphix

[mixphix]

We did have Enum for Down, before; it was just incorrect. The MR to fix instance Bounded a => Bounded (Down a), another problem mentioned in the discussion on the libraries mailing list @monoidal linked above, was backported to GHC 9.0. The patch also removed the newtype-derived Enum and Integral instances. I think this proposal (including @Bodigrim's point about checking the underlying type instead) adequately answers the remaining question from the mailing list: "does there exist an implementation of Enum for Down that respects the Bounded constraint?" in the affirmative, at the cost of adding an Eq constraint.

But Eq is not a superclass of Bounded, nor of Enum. This makes me wonder whether this instance is worth the trouble: what makes [Down lg .. Down sm] superior to Down <$> [lg, pred lg .. sm]? Is it simply to avoid (un)wrapping? I refer to my earlier argument that Down is intended to invert comparison, and that any further structure (on an arbitrary type) that that might entail is strictly accidental.

That being said, a type with Enum and Bounded surely has a unique total ordering given by [minBound .. maxBound], which then fixes the total ordering on its Down type to [Down maxBound .. Down minBound]. It would be nice to have this truth represented by the instance.

---

I suppose I've come around on this. Despite this instance's removal from base, it was rightfully removed for being incorrect, while this proposal does seem to provide an accurate implementation. As such, pending moving the equality check to the underlying type, I'm in favour.

[gergoerdi]

Another opportunity is to require Eq a and check if x == minBound, which is probably slightly better than if fromEnum x == fromEnum (minBound :: a). E. g., imagine Int128 - it has instance Enum and instance Bounded

Is the Enum instance of Int128 really desired, though, since fromEnum/toEnum cannot possibly do the right thing?

[tomjaguarpaw]

@gergoerdi (or someone with administrator rights?) can you please link the MR in the top post so it's easy to find?

The MR doesn't seem to compile. Is it missing Bounded and Num contexts?

[Bodigrim]

@gergoerdi It is well known that you cannot rely on fromEnum because of existence of instance Enum Integer or even more hideous instance Enum Int64 on 32-bit arch.

[Bodigrim]

@gergoerdi your patch does not compile:

libraries/base/Data/Ord.hs:160:25: error: [GHC-39999]
    • Could not deduce ‘Enum a0’ arising from a use of ‘fromEnum’
      from the context: Enum a
        bound by the instance declaration
        at libraries/base/Data/Ord.hs:152:10-32
      The type variable ‘a0’ is ambiguous
      Potentially matching instances:
        instance Enum a => Enum (Down a)
          -- Defined at libraries/base/Data/Ord.hs:152:10
        instance Enum Ordering -- Defined in ‘GHC.Enum’
        ...plus 13 others
        ...plus 14 instances involving out-of-scope types
        (use -fprint-potential-instances to see them all)
    • In the second argument of ‘(==)’, namely
        ‘fromEnum (minBound :: a)’
      In the expression: fromEnum x == fromEnum (minBound :: a)
      In a stmt of a pattern guard for
                     an equation for ‘enumFrom’:
        fromEnum x == fromEnum (minBound :: a)
    |
160 |         | fromEnum x == fromEnum (minBound :: a)
    |                         ^^^^^^^^
libraries/base/Data/Ord.hs:160:35: error: [GHC-39999]
    • Could not deduce ‘Bounded a1’ arising from a use of ‘minBound’
      from the context: Enum a
        bound by the instance declaration
        at libraries/base/Data/Ord.hs:152:10-32
      Possible fix:
        add (Bounded a1) to the context of
          an expression type signature:
            forall a1. a1
    • In the first argument of ‘fromEnum’, namely ‘(minBound :: a)’
      In the second argument of ‘(==)’, namely ‘fromEnum (minBound :: a)’
      In the expression: fromEnum x == fromEnum (minBound :: a)
    |
160 |         | fromEnum x == fromEnum (minBound :: a)
    |                                   ^^^^^^^^

As for non-binding opinions, I'm happy to vote in favour of the instance, if it uses if x == minBound instead of fromEnum as elaborated above.

[gergoerdi]

(build fixed)

As for non-binding opinions, I'm happy to vote in favour of the instance, if it uses if x == minBound instead of fromEnum as elaborated above.

Even at the cost of the extra Eq a constraint?

[Bodigrim]

As we discussed, fromEnum x == fromEnum (minBound :: a) is wrong when (architecture-dependent) Int is smaller than a. This is simply not an option.

I mean, all this pile of (Eq a, Bounded a, Enum a) is indeed unwieldy. Ideally we should spell out our assumptions about the interaction between these classes (see https://github.com/haskell/core-libraries-committee/issues/51#issuecomment-1094087424), but given how botched class Enum is, I'm prepared to look at this from pragmatic viewpoint. Any Enum a should morally be Eq a as well, and I believe this is true for all types in base, so the additional constraint is not a burden.

[gergoerdi]

Any Enum a should morally be Eq a as well, and I believe this is true for all types in base, so the additional constraint is not a burden.

This convinced me. I've pushed a version that requires Eq a.

[Bodigrim]

Dear CLC members, let's vote on the proposal to add instance (Eq a, Bounded a, Enum a) => Enum (Down a) as detailed in https://gitlab.haskell.org/ghc/ghc/-/merge_requests/8242/diffs. @tomjaguarpaw @chessai @cgibbard @mixphix @emilypi

---

+1 from me.

[cgibbard]

+1

On Fri, 30 Sept 2022 at 16:13, ˌbodʲɪˈɡrʲim @.***> wrote:

Dear CLC members, let's vote on the proposal to add instance (Eq a, Bounded a, Enum a) => Enum (Down a) as detailed in https://gitlab.haskell.org/ghc/ghc/-/merge_requests/8242/diffs. @tomjaguarpaw https://github.com/tomjaguarpaw @chessai https://github.com/chessai @cgibbard https://github.com/cgibbard @mixphix https://github.com/mixphix @emilypi https://github.com/emilypi

+1 from me.

— Reply to this email directly, view it on GitHub https://github.com/haskell/core-libraries-committee/issues/51#issuecomment-1263979711, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABVVE3BEFE7R6KVJM7MATOLWA5CVNANCNFSM5RYXMY5A . You are receiving this because you were mentioned.Message ID: @.***>

[mixphix]

~-1. Considering that this implementation causes errors for unsigned types (see the MR), I'm voting against this proposal.~