why Alternative's some and many are infinite recursive functions in haskell

Question

I was looking at Alternative typeclass in haskell and I was playing with it in ghci when I issued this

some (Just 2)

It hanged, I looked in the source code of Alternative, Alternative's some and many default definition is this :

some :: f a -> f [a]
some v = some_v
  where
    many_v = some_v <|> pure []
    some_v = (fmap (:) v) <*> many_v

-- | Zero or more.
many :: f a -> f [a]
many v = many_v
  where
    many_v = some_v <|> pure []
    some_v = (fmap (:) v) <*> many_v

It's obvious that some_v and many_v are indirectly infinitely recursive, and they aren't defined in terms of empty and <|>.

If they must be defined by the instance then they shouldn't have default definition, right ? and since Maybe doesn't define them my statement above hanged which seems strange to me since it isn't mentioned in the docs.

So why were they defined like that ? is There something I'm missing ?

`many Nothing` and `some Nothing` work fine. What did you expect `some (Just 2)` to do? — melpomene, Sep 24 '16 at 10:03
`Just [2]` is semantically wrong. It would have to be `Just [2, 2, 2, 2, 2, 2, ...]` but that computation never finishes. — melpomene, Sep 24 '16 at 10:10
@melpomene hmmm if it is `Just [2,2,2,2,...]` then wouldn't `take 2 <$> (some (Just 2))` return some results ? (it hanged with me) — niceman, Sep 24 '16 at 10:13
No, because it can't actually return that (at least with the current definition it has to "run actions" until `v` turns `empty` at some point). Hmm. — melpomene, Sep 24 '16 at 10:20
Related: [What are Alternative's “some” and “many” useful for?](http://stackoverflow.com/q/18108608/1333025) — Petr, Sep 24 '16 at 12:25

danidiaz · Accepted Answer · 2016-09-24T10:19:09.517

The Alternative instance for Maybe is as follows:

instance Alternative Maybe where
    empty = Nothing
    Nothing <|> r = r
    l       <|> _ = l

It defines empty and (<|>), leaving some and many as their default implementations.

Using many and some makes sense when the Alternative can succeed or fail for "external reasons" not contained in the value itself. The typical example is parsers: you try to parse integers repeatedly from an input stream, until an integer isn't found and empty is returned.

But with Just 2, the Alternative "always succeeds", so to speak. There's nothing external to the value that can make it "fail" and finish the computation. So it goes into an infinite loop.

why Alternative's some and many are infinite recursive functions in haskell

1 Answers1