Search code examples
haskelltypeclassapplicativearrowsalternative-functor

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.


Solution

  • 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.