A newbie question about Arrows.
Hello, I read some of the material about Arrows on www.haskell.org/arrows and I have some questions : * Why is made the choice to use (,) as Cartesian in first? Can't we write something like : class Cartesian p where pair :: a -> b -> (p a b) projLeft :: (p a b) -> a projRight :: (p a b) -> b class Cartesian pair => Arrow ar where arr ::( ar pair a b) -> (ar pair a b) (>>>) :: (ar pair a b) -> (ar pair b c) -> (ar pair a c) first :: (ar pair a b) -> (ar (pair a d) (pair b d)) (The same could be said for ArrowChoice) I think this could be more powerful and could allow a smarter management of inputs and outputs of arrows than tuples. I think for example to event-driven arrows : we could make a pair of inputs without mixing the "event happened" information. * Why is made the choice of first as being a base function? We have first f = f *** (arr id) second f = (arr id) *** f So they could be define from (***). Moreover, the definition of f *** with first and second creates an order in the use of the f and g (first f >>> second g) whereas it seems that (***) is a "parallel" operator. In an event-driven arrow we have to give the same events to f and g even if they are independent. Best regards, Nicolas Oury
On Mon, Jan 06, 2003 at 11:02:32AM +0100, Nicolas Oury wrote:
* Why is made the choice to use (,) as Cartesian in first?
It's certainly possible to define a more general interface, and the theoretical work does. However the arrow interface is already very general, and the question is whether any programs can be written to the more general interface. Magnus Carlsson has some ideas along these lines (see http://www.cse.ogi.edu/~magnus/ProdArrows/). I will quibble with some of the details, though:
Can't we write something like :
class Cartesian p where pair :: a -> b -> (p a b) projLeft :: (p a b) -> a projRight :: (p a b) -> b
class Cartesian pair => Arrow ar where arr ::( ar pair a b) -> (ar pair a b) (>>>) :: (ar pair a b) -> (ar pair b c) -> (ar pair a c) first :: (ar pair a b) -> (ar (pair a d) (pair b d))
First, you don't need pair for the first two, so one might define class PreArrow ar where arr :: (a -> b) -> ar a b (>>>) :: ar a b -> ar b c -> ar a c Second, we don't really need pair to be quite as product-like. What we really want is for it to be "monoidal", i.e. a binary functor with a unit type u and isomorphisms type Iso a b = (a -> b, b -> a) class Monoidal pair u | pair -> u where unitl :: Iso (pair u a) a unitr :: Iso (pair a u) a assoc :: Iso (pair a (pair b c)) (pair (pair a b) c) satisfying a few axioms. For products (pretending that Haskell has products), we use pair = (,), u = (), unitl = fst and unitr = snd. For sums (useful for asynchronous event streams), pair = Either and u = an empty type. Then one could define class (PreArrow ar, Monoidal p u) => GenArrow ar p u where first :: ar a b -> ar (p a c) (p b c) which would subsume Arrow and ArrowChoice. Some of the "Theoretical Aside"s in the Arrow Notation paper discuss this possibility.
* Why is made the choice of first as being a base function?
We have
first f = f *** (arr id)
second f = (arr id) *** f
So they could be define from (***).
Moreover, the definition of f *** with first and second creates an order in the use of the f and g (first f >>> second g) whereas it seems that (***) is a "parallel" operator.
This is discussed in John Hughes's paper (end of 4.1). The essential point is that the appearance of symmetry is illusory. For many arrows, including Kleisli arrows of common monads, the ordering is there, even though the notation *** hides it.
On Monday 06 January 2003 04:02 am, Nicolas Oury wrote:
I think for example to event-driven arrows : we could make a pair of inputs without mixing the "event happened" information.
Here's one that's been baffling me: What about the case where you have two arrows you want to combine. Suppose that each of these arrows are a stream processor, which process the type Either. SP (Either a b) (Either a b) Now combing these with the sequencing operator is straightforward. The output of the first SP becomes the input of the second. (>>>) :: SP i o -> SP i o -> SP i o Or in a routing diagram In >- SP1 --> SP2 --> Out But what if you wanted to mix up the routing of Left and Right from the Either above? In(Left) -> SP1(Left) In(Right) -> SP2(Right) SP1(Right) -> SP2(Left) SP2(Left) -> SP1(Right) SP1(Left) -> Out(Left) SP2(Right) -> Out(Right) One could easily define an operator to do this, but then what if one wanted to combine three arrows with arbitrary routing of the signal? The problem becomes combinatorial quickly. Yet this is exactly what happens in circuit design and signal routing, or complex object oriented code. I imagine this like a multi-layer circuit board, each SP maintains it's own state and operates on multiple streams. The routing of these streams is arbitrary and complex. Maybe I'm just missing something trival and there's a simple way to do this already with arrows. Shawn
On Thu, Jan 09, 2003 at 10:30:45AM -0600, Shawn P. Garbett wrote:
On Monday 06 January 2003 04:02 am, Nicolas Oury wrote:
I think for example to event-driven arrows : we could make a pair of inputs without mixing the "event happened" information.
Here's one that's been baffling me: What about the case where you have two arrows you want to combine. Suppose that each of these arrows are a stream processor, which process the type Either.
SP (Either a b) (Either a b)
Now combing these with the sequencing operator is straightforward. The output of the first SP becomes the input of the second.
(>>>) :: SP i o -> SP i o -> SP i o
Or in a routing diagram
In >- SP1 --> SP2 --> Out
But what if you wanted to mix up the routing of Left and Right from the Either above?
In(Left) -> SP1(Left) In(Right) -> SP2(Right) SP1(Right) -> SP2(Left) SP2(Left) -> SP1(Right) SP1(Left) -> Out(Left) SP2(Right) -> Out(Right)
Here's a method that's generalizable, if not elegant. We need a feedback combinator that feeds the Right output channel back to the input (this is a trivial variant of the loop combinators in the Fudgets library): fixSP :: SP a (Either b a) -> SP a b For convenience we define output = Left -- produce some output from the network send = Right -- route to a stream processor and define a datatype for the components: data Input a b c d e f = In (Either a b) | SP1 (Either c d) | SP2 (Either e f) Obviously the need for a new datatype is a drawback, but it lets us name the components' input streams. Now your example can be coded in arrow notation as combine sp1 sp2 = arr In >>> fixSP (proc z -> case z of In (Left v) -> returnA -< send (SP1 (Left v)) In (Right v) -> returnA -< send (SP2 (Right v)) SP1 x -> do out <- sp1 -< x returnA -< case out of Left v -> output (Left v) Right v -> send (SP2 (Left v)) SP2 x -> do out <- sp2 -< x returnA -< case out of Left v -> send (SP1 (Right v)) Right v -> output (Right v)) Your example had only 1-1 connexions, but the generalization isn't hard.
Shawn P. Garbett writes: ...
Or in a routing diagram
In >- SP1 --> SP2 --> Out
But what if you wanted to mix up the routing of Left and Right from the Either above?
In(Left) -> SP1(Left) In(Right) -> SP2(Right) SP1(Right) -> SP2(Left) SP2(Left) -> SP1(Right) SP1(Left) -> Out(Left) SP2(Right) -> Out(Right)
With the preprocessor at http://www.cse.ogi.edu/~magnus/ProdArrows/ this routing problem can be expressed as route sp1 sp2 = proc i1 × i2 -> do rec i1 × l2 >- sp1 -> l1 × r1 r1 × i2 >- sp2 -> l2 × r2 l1 × r2 >- arr id (Wouldn't it be nice if we had an editor that could present a graphical view of this program as a different aspect?) All the best, /M
participants (4)
-
Magnus Carlsson -
Nicolas Oury -
Ross Paterson -
Shawn P. Garbett