Opened 22 months ago

Last modified 22 months ago

#11650 new bug

Documentation does not mention that default definitions for Alternative(some, many) can easily blow up

Reported by: bgamari Owned by:
Priority: normal Milestone:
Component: Documentation Version: 7.10.3
Keywords: Cc: core-libraries-committee@…, RyanGlScott
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description (last modified by bgamari)

Consider this case (taken from #11649)

import Control.Applicative

data U1 p = U1

instance Functor U1 where
    fmap f U1 = U1

instance Applicative U1 where
    pure _ = U1
    U1 <*> U1 = U1

instance Alternative U1 where
    empty = U1
    U1 <|> U1 = U1

instance Show (U1 p) where
    show U1 = "U1"

main = print (some U1)

This looks fine, right? Wrong,

$ ./Main
Main: <<loop>>

Of course, this can be avoided by simply defining some and many in U1's Alternative instance,

instance Alternative U1 where
    empty = U1
    U1 <|> U1 = U1
    some U1 = U1
    many U1 = U1

It seems that the default definitions of some and many will produce looping code in these cases (although it's not entirely clear to me which cases "these" cases are).

I suppose this is due to the fact that U1 will always "succeed". We should note this in the documentation to ensure that users don't end up with accidentally bottoming instances.

Change History (14)

comment:1 Changed 22 months ago by bgamari

Cc: core-libraries-committee added; core-libraries-committe removed

comment:2 Changed 22 months ago by bgamari

Cc: core-libraries-committee@… added; core-libraries-committee removed
Summary: Default definitions for Alternative(some, many) can easily blow upDocumentation does not mention that default definitions for Alternative(some, many) can easily blow up

comment:3 Changed 22 months ago by bgamari

Description: modified (diff)

comment:4 Changed 22 months ago by bgamari

Description: modified (diff)

comment:5 Changed 22 months ago by RyanGlScott

We could also fix this issue by making the Applicative instance less strict:

instance Applicative U1 where
  U1 <*> _ = U1

I'm not sure which is the best approach. Proxy (which is isomorphic to U1) doesn't pattern-match on its arguments in any of its instances, which allows it to short-circuit in a lot of possibly diverging computations. Then again, Proxy doesn't have an Alternative/MonadPlus instance for some reason...

comment:6 Changed 22 months ago by ekmett

The only reason it doesn't have Alternative and MonadPlus instances is that I didn't think of them! (Similarly, MonadZip)

I have absolutely no objection to adding them. If someone concocts a patch to add them to base, I'll readily retroactively add them to the tagged package, and Ryan can incorporate backports of them into base-orphans.

comment:7 Changed 22 months ago by RyanGlScott

OK. I noticed that U1 is also missing a MonadPlus instance as well, so we can scoop up all the missing U1/Proxy instances in another patch.

So now that question remains: do we fix U1's Alternative instance by overriding some/many, or do we fix it by making <*> lazier? I'm inclined to pick the former, since U1 is almost always used in the context of GHC generics, and strictly pattern-matching on it is almost always what you intend to do.

comment:8 Changed 22 months ago by ekmett

I mostly lack a preference here, but if we make it match the semantics of Proxy it'd avoid complications later on if we were to ever decide to make the leap and unify (:*:) with Product, (:+:) with Sum, U1 with Proxy, etc. rather than retain two of each.

I'm not proposing that we unify these things today, when and if we decide to do so it should be carefully deliberated, with possible wins weighed against ecosystem disruption, but anything that takes them further apart for trivial reasons forecloses interesting possible futures for no real gain.

comment:9 Changed 22 months ago by Ben Gamari <ben@…>

In 890e2bb/ghc:

GHC.Generics: Ensure some, many for U1 don't bottom

Reviewers: austin, hvr, ekmett, RyanGlScott

Reviewed By: RyanGlScott

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D1952

GHC Trac Issues: #11650

comment:10 Changed 22 months ago by bgamari

RyanGlScott, I've committed the patch in comment:9 as a stop-gap measure; I hope you'll have a chance to add the instance mentioned in comment:7 and when you do so fix U1 to your liking.

comment:11 in reply to:  8 Changed 22 months ago by RyanGlScott

Replying to ekmett:

I mostly lack a preference here, but if we make it match the semantics of Proxy it'd avoid complications later on if we were to ever decide to make the leap and unify (:*:) with Product, (:+:) with Sum, U1 with Proxy, etc. rather than retain two of each.

That's a pretty convincing argument. It does seem like it would save us work in the long run to make U1 as Proxy-like as possible (and similarly with other GHC.Generics datatypes), so I'll do this before 8.0 lands.

Some questions we should answer:

  1. Do change U1's derived Eq, Ord, Read, and Show instances (which have been around for a while) and manually implement them with lazy pattern-matching? That seems like the sensible thing to do, although it would be a subtle semantic change.
  2. Do we add all of the extra instances which Proxy has but U1 doesn't? (Enum, Bounded, Ix, etc.) My gut reaction is to punt on this and only add them if someone requests it. Plus, if we decide to merge U1 and Proxy, it will be a moot point after that.

comment:12 Changed 22 months ago by Ben Gamari <ben@…>

In 171d95df/ghc:

Missing Proxy instances, make U1 instance more Proxy-like

This accomplishes three things:

* Adds missing `Alternative`, `MonadPlus`, and `MonadZip` instances for
  `Proxy`
* Adds a missing `MonadPlus` instance for `U1`
* Changes several existing `U1` instances to use lazy pattern-matching,
  exactly how `Proxy` does it (in case we ever replace `U1` with
  `Proxy`). This is technically a breaking change (albeit an extremely
  minor one).

Test Plan: ./validate

Reviewers: austin, ekmett, hvr, bgamari

Reviewed By: bgamari

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D1962

GHC Trac Issues: #11650

comment:13 Changed 22 months ago by bgamari

We could still use some documentation for Alternative to point out this gotcha?

comment:14 Changed 22 months ago by RyanGlScott

We could, although I'm not quite sure what is the best way to describe the problem (and solution). There is a haskell-cafe thread from 2011 which tried to address the issue of documenting some/many more precisely, but that never seemed to reach a consensus.

Note: See TracTickets for help on using tickets.