Infinite loop for Alternative instance for Maybe

Summary

The Alternative Instance for Maybe currently uses the default method provided by Alternative class, that currently does an infinite loop.

Steps to reproduce

In ghci, run some $ Just 5 or many $ Just 5. It will run into infinite loop without outputting anything.

Expected behavior

some $ Just 5 and many $ Just 5 should both return the same output as Just $ repeat 5

Using the property of some and many, we get:

some v = (:) <$> v <*> many v

for v = Just a, we get

some (Just a) = (:) <$> (Just a) <*> many (Just a)

Plugging in another property many v = some v <|> pure [] gets us

some (Just a) = (:) <$> (Just a) <*> (some (Just a) <|> pure [])

If, some (Just a) return Nothing, then

some (Just a) = (:) <$> (Just a) <*> (pure [])

some (Just a) = Just [a]

a contradiction, so some (Just a) must return a Just

some (Just a) = (:) <$> (Just a) <*> some (Just a)

some (Just a) = Just (a: (fromJust $ some (Just a)))

some (Just a) = Just (a: (fromJust $ Just (a: (fromJust $ ...))))

some (Just a) = Just (a: (a: ...))

some (Just a) = Just $ repeat a

Similarly, for many

many v = some v <|> pure []

many v = (Just $ repeat a) <|> pure []

many v = (Just $ repeat a)

Environment

• GHC version used: 9.0.1
• Operating System: Ubuntu 20.04
• System Architecture: x64