CODEWITHSUNDEEP
haskellarrow-abstractioncategory-abstractions
OllieB
OllieB

Reputation: 1431

Bidirectional Arrow

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.

Upvotes: 4

Views: 294

Answers (2)

OllieB
OllieB

Reputation: 1431

Some further approaches, best recorded as a separate answer.

The first imposes the additional constraint of an ArrowLoop, and is defined using a recursive arrow do notation.

From a data flow viewpoint however, no recursion is taking place.

(<->) ∷ (ArrowLoop a) ⇒ a (b,f) (c,g) → a (c,e) (d,f) → a (b,e) (d,g)
(<->) f1 f2 = proc (b, e) → do
  rec
    (c,g) ← f1 ↢ (b,f)
    (d,f) ← f2 ↢ (c,e)
  returnA ↢ (d,g)

It could equally be defined as

(<->) ∷ (ArrowLoop a) ⇒ a (b,f) (c,g) → a (c,e) (d,f) → a (b,e) (d,g)
(<->) f1 f2 = proc (b, e) → do
  rec
    (d,f) ← f2 ↢ (c,e)
    (c,g) ← f1 ↢ (b,f)
  returnA ↢ (d,g)

The second approach does not: I've yet to work out if this is a sane thing to do.

(<->) ∷ (Arrow a) ⇒ a (b,f) (c,g) → a (c,e) (d,f) → a (b,e) (d,g)
(<->) f1 f2 = proc (b, e) → do
  (c,_) ← f1 ↢ (b,undefined)
  (d,_) ← f2 ↢ (c,undefined)
  (_,f) ← f2 ↢ (undefined,e)
  (_,g) ← f1 ↢ (undefined,f)
  returnA ↢ (d,g)

The following is the same as the second approach, but defined explicitly in terms of composition functions.

(<->) ∷ (Arrow a) ⇒ a (b,f) (c,g) → a (c,e) (d,f) → a (b,e) (d,g)
(<->) f g =
  let toFst x = (x,undefined)
      toSnd x = (undefined,x)
  in
    (arr toFst ⋙ f ⋙ arr fst ⋙ arr toFst ⋙ g ⋙ arr fst) ⁂
    (arr snd ⋘ f ⋘ arr toSnd ⋘ arr snd ⋘ g ⋘ arr toSnd)

Upvotes: 2

chi
chi

Reputation: 116174

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 (?).

Upvotes: 5

Related Questions