Fantasy-land: Add spec for Alt, Plus, Alternative

[safareli]

I think it would be nice if we also define algebras for Alt, Plus and Alternative

-- | The `Alt` type class identifies an associative operation on a type
-- | constructor.  It is similar to `Semigroup`, except that it applies to
-- | types of kind `* -> *`, like `Array` or `List`, rather than concrete types
-- | `String` or `Number`.
-- |
-- | `Alt` instances are required to satisfy the following laws:
-- |
-- | - Associativity: `(x <|> y) <|> z == x <|> (y <|> z)`
-- | - Distributivity: `f <$> (x <|> y) == (f <$> x) <|> (f <$> y)`
-- |
-- | For example, the `Array` (`[]`) type is an instance of `Alt`, where
-- | `(<|>)` is defined to be concatenation.
class Functor f <= Alt f where
  alt :: forall a. f a -> f a -> f a


-- | The `Plus` type class extends the `Alt` type class with a value that
-- | should be the left and right identity for `(<|>)`.
-- |
-- | It is similar to `Monoid`, except that it applies to types of
-- | kind `* -> *`, like `Array` or `List`, rather than concrete types like
-- | `String` or `Number`.
-- |
-- | `Plus` instances should satisfy the following laws:
-- |
-- | - Left identity: `empty <|> x == x`
-- | - Right identity: `x <|> empty == x`
-- | - Annihilation: `f <$> empty == empty`
class Alt f <= Plus f where
  empty :: forall a. f a


-- | The `Alternative` type class has no members of its own; it just specifies
-- | that the type constructor has both `Applicative` and `Plus` instances.
-- |
-- | Types which have `Alternative` instances should also satisfy the following
-- | laws:
-- |
-- | - Distributivity: `(f <|> g) <*> x == (f <*> x) <|> (g <*> x)`
-- | - Annihilation: `empty <*> f = empty`
class (Applicative f, Plus f) <= Alternative f

Snippets from purescript-control

It will be useful to Future/Task implementations (alt will be race).
and with also define Parallel algebra then in concurrent applicative could implement Alternative and we would have the race as well (MonadRace is removed).

[safareli]

And maybe also add MonadZero and MonadPlus

-- | The `MonadZero` type class has no members of its own; it just specifies
-- | that the type has both `Monad` and `Alternative` instances.
-- |
-- | Types which have `MonadZero` instances should also satisfy the following
-- | laws:
-- |
-- | - Annihilation: `empty >>= f = empty`
class (Monad m, Alternative m) <= MonadZero m


-- | The `MonadPlus` type class has no members of its own but extends
-- | `MonadZero` with an additional law:
-- |
-- | - Distributivity: `(x <|> y) >>= f == (x >>= f) <|> (y >>= f)`
class MonadZero m <= MonadPlus m

[rpominov]

Alt looks like fantasy-land's Semigroup with additional distributivity law:

a.concat(b).map(f) is equivalent to a.map(f).concat(b.map(f))

And Plus looks like Monoid with additional law:

m.empty().map(f) is equivalent to m.empty()

Am I reading this right?

How would they fit in the dependency tree then? Alt would have dependency on Semigroup and Functor, right? But I'm confused with dependencies of Plus, should it be Alt and Functor, or Monoid and Functor, or all three?

[rpominov]

Or maybe I've misunderstood all this, and Semigroup shouldn't be connected with Alt, neither Monoid with Plus. In other words concat() != alt() and empty() != empty() where the first empty from Monoid and second one from Plus.

[safareli]

Distinction between typeclasses MonadPlus, Alternative, and Monoid?

So for example Maybe could be Semigroup if value in it is also Semigroup, but Plus and Alt should not "look" at values inside

[safareli]

we can make Task instance of Semigroup if values in Task are also Semigroups.

Task.of([a]).concat(Task.of([b])) = Task.of([a,b])

we can make Task MonadPlus

Task.rejected(err).alt(Task.of(b)) = Task.of(b)

we can make TaskAp Alternative

Task.empty/*never*/.alt(Task.of(b)) = Task.of(b)

But we would have collision with Monoid's empty and Plus' empty. in PureScirpt Monoid's empty is called mempty. so we could:

• rename Monoid's empty to mempty
• call Plus' empty something else for example: pempty

[rpominov]

I see, so the idea is that they are not connected and Monoid for example can do something different than Plus.

My first impression is that I'd rather had them connected, so we always talk about the same operation but may make less or more stronger claim. But I really don't feel educated and experienced enough to discuss new type classes, though 😄

Very curious what others think!

[safareli]

😄 just came to all that Alternative staff today from #186 (I want this specs to make Free lawful and concurrent) :P

[garyb]

@rpominov / @safareli your intuition seems pretty spot on - Alternative is exactly a monoid, but it applies to types of kind * -> * rather than *, so it operates on the "structure" rather than the value.

As an example of how this manifests, take Maybe. In PureScript we have these instances:

instance semigroupMaybe :: Semigroup a => Semigroup (Maybe a) where
  append Nothing y = y
  append x Nothing = x
  append (Just x) (Just y) = Just (x <> y)

instance altMaybe :: Alt Maybe where
  alt Nothing r = r
  alt l _ = l

So compare append (Just a) (Just b) will get you Just (append a b), whereas alt (Just a) (Just b) will get you Just a - so although they're both semigroup operations the behaviour is quite different given that Alt isn't allowed to do anything with the inner values.

As for the empty values... I can't think of an example where mempty and empty differ currently, but I'm not sure it's impossible. Even if it is impossible, we'd still need to distinguish between mempty and empty in PureScript because we intentionally avoid "zero-first" class hierarchies, instead we start with an operation and then the "zero" is a subclass of that, as you can be more principled about how the zero interacts with the operation then.

[rpominov]

Thanks , @garyb , I understand it better now.

Even if it is impossible, we'd still need to distinguish between mempty and empty in PureScript because we intentionally avoid "zero-first" class hierarchies

In fantasy-land we would probably have to do the same for the same reason. We also start from Semigroup and then define Monoid as Semigroup with empty. So the only way to use same empty method would be to make Plus depend on Monoid. We could use pempty as a name for Plus's empty, as @safareli pointed out.

[garyb]

Yeah, I kinda wish we'd done something different there too! mempty is probably more commonly used than empty so it's a little strange it has the less natural name.

[syaiful6]

it already discussed here: https://github.com/fantasyland/fantasy-land/issues/117

some related issue about the laws: https://github.com/purescript/purescript-control/issues/6

[syaiful6]

It good to have this on Fantasy Land i think. Kudos for bringing it again @safareli

[safareli]

some resources:

• a realy good explanation of Alternative vs Monoid
• an example of a Monad which is an Alternative but not a MonadPlus.

There is diagrinment in haskell comunity on monadPlus laws and this proposal suggests to split it in MonadZero, MonadPlus and MonadOr. Currently purescript has MonadZero and MonadPlus, but no MonadOr it would look like this I think:

-- | The `MonadOr` type class has no members of its own but extends
-- | `MonadZero` with an additional law:
-- |
-- | - Left catch: `(return a) <|> b = return a`
class MonadZero m <= MonadOr m

Currently I don't know if there is a plan to add it, maybe @garyb knows it.

[safareli]

I'm adding @robotlolita @Avaq as Task/Future will be effected with this specs.

For Applicative versions of Task/Future:

• race will be alt
• empty (never ending task) will be pempty

For Monadic version of Task/Future:

• alt will try first task and if it fails then try second one. (i think alternatives some and any could be useful here )
• pempty could be failing task

[safareli]

btw @paf31 @garyb in purescript we have Bind and why is for example MonadRec named MonadRec when it could be named BindRec (same on MonadZero and MonadPlus)?

[safareli]

@SimonRichardson can you take a look this issue? if it's ok I would create PR for Alt, Plus and Alternative and after we decide on {Monad,Chain}{Zero,Plus,Or}will update the PR with corresponding changes.

update:

{Monad,Chain}{Zero,Plus,Or}

in here I was first thinking that maybe we could define Chain{Zero,And} but now I realised that if something is Chain and Alternative than it's also a Monad as Alternative is subclass of Applicative

[SimonRichardson]

Sure, I can look tomorrow 😀

[paf31]

We probably could define BindRec in purescript-tailrec, but we haven't had a use for it yet.

I'm trying to think of examples of things which have BindRec but not MonadRec, or functions which only need BindRec.

I suppose Writer s has BindRec for any Semigroup s, but is only a MonadRec when s is also a Monoid.

And for the latter, we could write a variant of foldM on non-empty lists which only required >>= and not pure.

Perhaps it is worth adding.

[safareli]

@paf31 And if we have BindRec then MonadRec is just class (Monad m, BindRec m) <= MonadRec m without any extra laws, (is just a "shortcut" for Monad m, BindRec m)

[safareli]

This is what proposed graph look like:

[joneshf]

I think that's asking too much of Alt and Plus. For instance, something like data Map k v = ... doesn't have a sensible Applicative instance for Map k. However, you should be able to write an Alt instance for Map k, assuming Ord k of course. It's better to have Functor be the superclass of Alt

[safareli]

@joneshf correct ! (I had a mistake in graph)

here is updated one:

[SimonRichardson]

I'd be more than happy to see a PR @safareli - awesome work already :)

[safareli]

What others think on changing pempty to zero

[safareli]

197 is ready for review <3