2

I would like to use the some function from Alternative http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Base.html#some.

I've tried: 

*MyParser Data.Attoparsec.Text Control.Applicative Data.Text> some [3443]


ewrewrew
ewrwwwwww545
43535
435

^CInterrupted.

As you can see, I interrupted the input. How can I use the some function?

duplode
  • 33,731
  • 7
  • 79
  • 150
softshipper
  • 32,463
  • 51
  • 192
  • 400
  • 3
    `some` and `many` are a little strange and I don't really have experience using them, but they are recursively defined in terms of each other, and in a way that basically doesn't work at all for the List (`[]`) instance of `Alternative`, in which `<|>` is simply list concatenation. I believe they're most commonly used for parsers, in which `<|>` instead models the concept of choice between alternatives. (Although I see you've got Attoparsec loaded, you've chosen to use `some` on a list rather than on a parser.) – Robin Zigmond Oct 26 '19 at 21:50
  • I am reading the book pratical haskell and there is an exercise about `Parser`. It uses the `some` function. – softshipper Oct 26 '19 at 22:03
  • 3
    As I said, parsers do use `some` and `many` (not that I've personally yet explored them in any detail). But in your example, you don't have a parser, you have a list. As far as I can tell, `some` and `many` simply don't work on lists - they will just loop indefinitely. – Robin Zigmond Oct 26 '19 at 22:08
  • [related question](https://stackoverflow.com/q/7671009/849891). – Will Ness Jun 17 '20 at 16:48

1 Answers1

0

Consider what happens when you try to expand some [1]:

some [3443] == some_v
            == liftA2 (:) [3443]  many_v  -- definition of some_v
            == [x:y | x <- [3443], y <- many_v]  -- definition of liftA2
            == [x:y | x <- [3443], y <- some_v ++ pure []] -- definition of many_v

Here's I've immediately replaced <|> with (++). Because (++) is strict in its first argument, you have to evaluate some_v before proceeding, but that gets us into an infinite loop.

Alternative is described as a monoid for applicative functors. If I understand correctly, some xs would be the infinite list of non-empty lists you could create by taking one element from xs at a time.

some [3443] == [[3443], [3443, 3443], [3443, 3443, 3443], ...]

and many xs would be the infinite list of (possibly empty) lists (essentially, just []:some xs.) Because of the strictness of (++), though, the result is not computed lazily, so you never actually terminate.

chepner
  • 497,756
  • 71
  • 530
  • 681
  • This isn't *quite* right; as it doesn't address the notion of "failure" that `<|>` assumes which can allow it to move on to its second argument. Compare `some Nothing` which evaluates to `Nothing` with `some (Just 3)` which likewise goes into an infinite loop. – chepner Oct 27 '19 at 14:31