Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Product and Sum Type Parallels in Haskell Type Classes

It appears that type classes such as Applicative, Monad and Arrow have some sort of sum type equivalent in type classes such as Alternative, MonadPlus and ArrowPlus respectively. For example, Applicative and Alternative can be used to define the following:

(<&&>) :: Applicative f => f a -> f b -> f (a, b)
a <&&> b = (,) <$> a <*> b

(<||>) :: Alternative f => f a -> f b -> f (Either a b)
a <||> b = (Left <$> a) <|> (Right <$> b)

However, in all of these cases (as well as with ArrowChoice), the product type class is a prerequisite for the sum type class. Are there type class rules or common functions that depend on the prerequisite class? The Typeclassopedia touches on these relationships, but unfortunately I couldn't find any explicit reason for the dependency.

like image 791
David Harrison Avatar asked Apr 29 '15 05:04

David Harrison


1 Answers

Arrow is basically the class for monoidal categories1 – with “monoid” not referring to Monoid, but the product-monoid of Haskell types. I.e., with unit element () and multiplication (,). Now, sum types make up a monoid as well, and that's what ArrowChoice uses. These two classes are in that sense complementary; ArrowChoice shouldn't really be a subclass of Arrow.

In a monoidal category, you can then go on to have monoidal functors. How these come out depends on what you use as your type-monoid. For (), (,), you get

class ProdMonoidalFtor f where
  prodUnit :: () -> f ()
  prodZip :: (f a, f b) -> f (a,b)

type (+) = Either
class SumMonoidalFtor f where
  sumUnit :: Void -> f Void
  sumZip :: f a + f b -> f (a+b)

Turns out the latter is basically useless, because Void is the initial object of Hask, meaning there exists exactly one Void -> a (namely absurd) for all types a. However, what does make some sense is comonoidal functors with +:

class SumCoMonoidalFtor f where
  sumCounit :: f Void -> Void -- I bet you find this useless too, but it's not totally.
  sumCozip :: f (a+b) -> f a + f b

That in turn wouldn't make sense for product types, because () is the terminal object.

What's interesting now is that ProdMonoidalFtor is equivalent to Applicative:

instance (ProdMonoidalFtor f) => Applicative f where
  pure x = fmap (const x) $ prodUnit ()
  fs <*> xs = fmap (\(f,x) -> f x) $ prodZip (fs,xs)

One might then suspect that Alternative is equivalent to SumMonoidalFtor, but it's not! Actually, it is equivalent to decisive functors, which are to comonads as applicatives are to monads.

Whereas Alternative and MonadPlus don't really seem to have much mathematical backing, they're essentially what you get when “un-Kleisliing” the ArrowChoice class, but using the Kleisli category that arises from ProdMonoidalFtor. It's all a bit dubious.


1That's considering only first/left, second/right, and ***/+++. As for the remaining &&&, ||| and arr, these are more specific and IMO belong in seperate classes.

like image 83
leftaroundabout Avatar answered Nov 11 '22 14:11

leftaroundabout