Pulling Apart haskell’s Arrow Types.

Haskell arrows are a strange beast. Most people have a hard time understanding them, and the people that do often see things that are almost arrows but don’t meet 1 of the criteria. For example stream transformers don’t have a valid instance of ***, but they do have an instance for arr, and for +++ and |||. I recently went over them and figured out exactly what each constraint implies.

As Dan Piponi has pointed out, arrows are profunctors. Another way to think about them is that arrows define a category whose objects are haskell types. It’s interesting to ask about what the relations between Hask and this other category are. So here are some possible relations:

Throughout the rest, the non-Hask category will be called C.

  • There is a functor from Hask to C. This is witnessed by arr in the standard arrow package. Note that this is mostly independent from the rest of the relations below, except that if the relations below exist there’s a commuting diagram with arr.
  • The Haskell product is the product in C. Witnessed by &&&.
  • The Haskell product is a monoid in C. Witnessed by ***. This is weaker than above. e. g. Op satisfies this, but not the above. (,) is the sum in Op, but it’s still a monoid
  • The Haskell sum is a sum in C. Witnessed by |||.
  • The Haskell sum is a monoid in C. Witnessed by +++. As above, this is weaker
  • The Haskell product is the product in C, and the type c a b is the exponential in C. This is witnessed by the co-unit of the adjunction: eval. The Haskell arrow package calls this app

I’ve written these out as code below.

*Note that it’s probably possible to be even more general in Haskell and ask whether C has some other product, or some other sum.
and then define the same usfeful functions when it happens to be the Haskell sum and the Haskell product, but I wanted to map out exactly what Arrow was asking for first.

module Category where

import Prelude hiding (fst,snd,(.),id)
import Control.Category

{-
Since the objects of this other category are haskell types describing a functor
between the two is as simple as describing its action on functions. arr does
exactly this
-}
class (Category c) => CategoryFunctor c where
  arr :: (a -> b) -> c a b

class (Category c) => ProductIsMonoid c where
  (***) :: (c a1 b1) -> (c a2 b2) -> (c (a1,a2) (b1,b2))

class (ProductIsMonoid c) => ProductIsCommutatitve c where
  cSwap :: (c (a,b) (b,a))

{-
If defining both instances, *** can be defined in terms of &&& as follows:
 f *** g = (fst >>> f) &&& (snd >>> g)
-}
class (ProductIsMonoid c) => ProductIsProduct c where
  (&&&) :: (c a b1) -> (c a b2) -> (c a (b1, b2))
  fst   :: (c (a,b) a)
  snd   :: (c (a,b) b)

class (Category c) => SumIsMonoid c where
  (+++) :: (c a1 b1) -> (c a2 b2) -> (c (Either a1 a2) (Either b1 b2))

{-
If defining both instances, +++ can be defined in terms of ||| as follows:
 f +++ g = (f >>> left) ||| (g >>> right)
-}
class (SumIsMonoid c) => SumIsSum c where
  (|||) :: (c a1 b) -> (c a2 b) -> c (Either a1 a2) b
  left  :: c a (Either a b)
  right :: c b (Either a b)

class (ProductIsProduct c) => ProductIsClosed c where
  eval :: (c (c a b, a) b)

{-
Here we define instances for (->). (->) Has all the instances, because it is the
same category
-}
instance CategoryFunctor (->) where
  arr = id

instance ProductIsMonoid (->) where
  (***) f g (x,y) = (f x, g y)

instance ProductIsProduct (->) where
  (&&&) f g x = (f x, g x)
  fst (x,y) = x
  snd (x,y) = y

instance ProductIsCommutatitve (->) where
  cSwap (x, y) = (y, x)

instance SumIsMonoid (->) where
  (+++) f g (Left x) = Left $ f x
  (+++) f g (Right x) = Right $ g x

instance SumIsSum (->) where
  (|||) f g (Left x) = f x
  (|||) f g (Right x) = g x
  left = Left
  right = Right

instance ProductIsClosed (->) where
  eval = uncurry ($)

-- Here's a type where we can define some, but not all of the instances.
newtype Op a b = Op (b->a)

instance Category Op where
  id = id
  (Op f) . (Op g) = Op $ g . f

instance ProductIsMonoid Op where
  (Op f) *** (Op g) = Op $ f *** g

instance SumIsMonoid Op where
  (Op f) +++ (Op g) = Op $ f +++ g
Advertisements