Bidirectional Arrow

Question

I'm trying to capture a symmetrical data processing pipeline using arrows, and was wondering if bidirectional composition is possible.

Control.Arrow exposes the following

-- | Left to right composition
(>>>) :: Category cat => cat a b -> cat b c -> cat a c 

-- | Right to left composition
(<<<) :: Category cat => cat b c -> cat a b -> cat a c

what I'd like, but cannot work out how to express is bidirectional composition of pairs. The type is something like.

(<^>) :: Category cat => cat (a,y) (b,z) -> cat (b,x) (c,y) -> cat (a,x) (c,z)

where the first element of each pair is to composed left-to-right, and the second to be composed right-to-left.

I'm pretty sure this isn't possible, at least not without some audacious infinite knot tying or unsafe use of bottom values. It could very well be done under some extra constraints though – what's your actual use case? — leftaroundabout
I've a configurable set of encoding / decoding operators, each of which has type (a,b) -> (a', b'). I can tie them together manually, but pipes seemed a good fit. It would be perfect, except the encoding pipeline needs to be composed left to light, and the decode right to left. — OllieB
Maybe your are looking for something like Product (->) (Op (->)), exploiting Data.Category? — chi
Basically, Op (->) is flipped (->), i.e. Op (->) a b is actually b -> a (function going "backward"). Then the category Product (->) (Op (->)) composes a morphism in (->) (forward function) and one in Op (->) (backward function). Hence, >>> in this category should work as you want. — chi

chi chi · Accepted Answer · 2017-02-13T23:26:10

Here's an example of a category involving pairs of forward and backwards functions.

{-# LANGUAGE TypeOperators, GADTs #-}

import Prelude hiding ((.))
import Data.Category
import Data.Category.Product

type C = (->) :**: (Op (->))

The above states that C (a,b) (c,d) is isomorphic to a pair (a->c, d->b). Pairs "compose" in the category in the natural way: the forward functions are composed forwards, the backwards functions are composed backwards.

Here are two examples:

f :: C (String, Bool) (Int, Char)
f = length :**: Op (=='a')

Note how the backwards function has to be wrapped in an Op (belongs to the "opposite" category).

g :: C (Int, Char) ([Int], Maybe Char)
g = (\x->[x,x]) :**: Op (maybe 'X' id)

Note how the "source" of g is the "target" of f. This ensures composition is possible.

composed :: C (String, Bool) ([Int], Maybe Char)
composed = g . f

test :: ([Int], Bool)
test = case composed of
   (forward :**: Op backward) -> (forward "abcde", backward Nothing)
-- result: ([5,5],False)

On a more practical side, note that Data.Category and Control.Category are different beasts :-( and that the Control.Arrow library mentioned in the question uses the latter.

Still, it should be possible to define Op and :**: for Control.Category as well. Maybe it's already on hackage somewhere (?).

Bidirectional Arrow

2 Answers