Explicitly define `many` and `some` in `Alternative` instance of `Data.Functor.Compose`

[jameshaydon]

Currently the Alternative instance for Compose f g is:

instance (Alternative f, Applicative g) => Alternative (Compose f g) where
    empty = Compose empty
    (<|>) = coerce ((<|>) :: f (g a) -> f (g a) -> f (g a))
      :: forall a . Compose f g a -> Compose f g a -> Compose f g a

The some and many methods thus get their default definitions. If f has an explicit definition for some or many in Alternative f, then this gets ignored. If they are more efficient than the defaults, then this efficiency is discarded in Alternative (Compose f g).

In some cases, the resulting some and many in Alternative (Compose f g) are completely broken. This occured to me with

(Monoid ann) => Alternative (Compose (Prod r e t) ((,) ann))

where Prod r e t is from Earley. In the case of Earley, some and many have special case definitions, and using the default definitions instead results in infinite loops.

I propose the following definitions for some and many:

some :: (Alternative f, Applicative g) => Compose f g a -> Compose f g [a]
some (Compose v) = Compose (sequenceA <$> some v)

many :: (Alternative f, Applicative g) => Compose f g a -> Compose f g [a]
many (Compose v) = Compose (sequenceA <$> many v)

These definitions make sure to use the implementations of some and many from Alternative f.

A related (accepted) proposal adds explicit definitions to Foldable (Compose f g): #57

[treeowl]

Could you demonstrate that these are equivalent to the default definitions, except sometimes more defined? Are there situations where your definitions will be slower than the current ones?

[Bodigrim]

I don't have a good intuition about instance Alternative (Compose f g). Could there be any examples given that at least informally demonstrate that the proposed definitions are sensible?

[jameshaydon]

Thanks for the questions:

@treeowl

Could you demonstrate that these are equivalent to the default definitions, except sometimes more defined?

Here is an informal explanation.

So first note that the Alternative part of Alternative (Compose f g) is essentially coming from Alternative f, indeed <|> is (up to coercion) just the one for f.

Let's just look at many, the default definition can be written:

many v = (liftA2 (:) v (many v)) <|> pure []

And the definition I propose for Compose f g is:

many (Compose v) = Compose (sequenceA <$> many v)

(I will elide the Compose constructor from now on.)

If the many for Alternative f is the default one, then both definitions will use (<|>) :: f (g a) -> f (g a) -> f (g a). Where they differ is the current definition combines repeated calls to v with:

-- from Applicative (Compose f g)
liftA2 (:) :: f (g a) -> f (g [a]) -> f (g [a])
liftA2 (:) = liftA2 (liftA2 (:))

(which uses liftA2 from f and g at the same time)
while the other combines them with

-- from Applicative f
liftA2 (:) :: f (g a) -> f [g a] -> f [g a]

and then turns the resultant f [g a] into f (g [a]) with fmap sequenceA (which uses liftA2 from Applicative g).

Thus, the equivalence of the two definitions essentially follows from the "composition law" for Traversable [], which can be stated in terms of sequenceA as:

sequenceA . fmap Compose = Compose . fmap sequenceA . sequenceA

@Bodigrim

I don't have a good intuition about instance Alternative (Compose f g). Could there be any examples given that at least informally demonstrate that the proposed definitions are sensible?

The example which lead me to this problem is:

Compose P ((,) Span)

where P is some parsing Applicative/Monad, and where Span is a Monoid for describing where in a file a thing was parsed from. If we imagine v as parsing items in some comma-seperated list, then the two definitions of many v unfurl like this:

Default definition:

• Keep trying to parse some thing with v (with source-span), eventually "failing" with pure [],
• Combine the results with liftA2 (liftA2 (:)). This uses Applicative P, which will parse one thing (with source-span), and then another thing (with source-span), and then apply liftA2 (:) to get a combined parse. The instance Applicative (() Span) uses then Monoid instance, so source spans are combined using <>. In the end you parse the whole list, and get a single source-span.

New definition:

• Keep trying to parse some thing with v (with a source-span),
• Combine the results with liftA2 (:), this will create a list of parsed things, each equipped with a source span: P [(Span, a)]
• Apply fmap sequenceA, which essentially mconcats all the source-spans to produce P (Span, [a]).

@treeowl

Are there situations where your definitions will be slower than the current ones?

In terms of efficiency, the definition I propose does two things differently which might affect efficiency:

• In the case that many from Alternative f has the default definition, a list is produced, which is torn apart re-constructed anew by sequenceA. There are two calls to (:) for every element of the result list.
• Since the calls to liftA2 from Applicative g are delayed till the call to fmap sequenceA, some data-structures can be accumulated for longer. In the example above, source-spans are accumulated before being combined. This could lead to more space being consumed.

I don't have a good grasp of how much this would matter in practice. So I think the best would be for me to run some benchmark tests on some examples.

[Bodigrim]

@jameshaydon could you please raise a GHC MR which we can vote on?

[jameshaydon]

@Bodigrim Sure I'll try to do that.

[jameshaydon]

@Bodigrim There is now a draft MR here: https://gitlab.haskell.org/ghc/ghc/-/merge_requests/10992

[Bodigrim]

Thanks @jameshaydon, this generally makes sense to me.

Dear CLC members, any additional questions to clarify the proposal?

[Bodigrim]

I reviewed the discussion once again and I agree with @jameshaydon: the new definition is semantically equivalent to the default one, but can benefit from optimized definitions of many and some if provided by instance Alternative f.

Sanity check in ghci:

> import qualified Text.ParserCombinators.ReadP as R
> import Data.Semigroup
> import Control.Applicative
> import Data.Functor.Compose

> many' (Compose v) = Compose (sequenceA <$> many v)
> getChar = Compose $ fmap (Sum 1,) R.get
> parseWithMany = R.readP_to_S (getCompose $ many getChar) "foo"
> parseWithMany' = R.readP_to_S (getCompose $ many' getChar) "foo"

> parseWithMany
[((Sum {getSum = 0},""),"foo"),((Sum {getSum = 1},"f"),"oo"),((Sum {getSum = 2},"fo"),"o"),((Sum {getSum = 3},"foo"),"")]
> parseWithMany'
[((Sum {getSum = 0},""),"foo"),((Sum {getSum = 1},"f"),"oo"),((Sum {getSum = 2},"fo"),"o"),((Sum {getSum = 3},"foo"),"")]

> parseWithMany == parseWithMany'
True

Performance-wise, the considerations at the end of #181 (comment) do not change the asymptotics. In fact, I doubt they are measurable at all. Re-using many from instance Alternative f however could offer an asymptotic speed up (and indeed does so, as demonstrated by the motivating example from Earley).

Given that there were no other questions raised for three months, let's go with a vote.

---

Dear CLC members, let's vote on the proposal to define some and many in instance Alternative f => Alternative (Compose f g) via some and many from instance Alternative f instead of the default definition, which ignores the latter completely and goes all the way through low-level (<|>). Such change allows for asymptotic improvement if the underlying instance Alternative f provides optimized definitions for some and many, which is a common case for parser combinators. The MR is available at https://gitlab.haskell.org/ghc/ghc/-/merge_requests/10992/diffs. This is not a breaking change.

@tomjaguarpaw @mixphix @velveteer @angerman @parsonsmatt @hasufell

---

+1 from me for the reasons above.

[parsonsmatt]

+1

[hasufell]

+1

[mixphix]

+1

[velveteer]

+1

[Bodigrim]

Thanks all, 5 votes are enough to approve.