Skip to content

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

Consider this case (taken from #11649 (closed))

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.

Edited by Ben Gamari
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information