Mon Aug 22 23:41:57 CEST 2011


Instead of using Arrow notation to perform "tuple plumbing" when
composing Arrow computations, it might be also useful to use a stack
approach.  Somebody has to have thought of that before...

Essentially Arrows use binary trees for product (and ArrowChoice uses
binary tries for sum using Either).

Represent the empty stack by ().  Applying an arrow to the top of the
stack is "first".

The question is then: what is the "default" representation for unary,
binary, ... operations.  Arrows are naturally unary and tupled
(uncurried) binary.  So maybe it's best to make lift/unlift from that
rep to:

  (a -> b)      ->   (a, s)       -> (b, s)
  ((a,b) -> c)  ->   (a, (b, s))  -> (c, s)

The reason why Arrows are not curried is that there is no apply
operator.  This would give Monad power (ArrowApply), since arrows
(whole computations) can depend on input values, which makes structure

Anyway, it seems important to note that arrows with non-binary tuple
inputs can't take inputs from other arrows, so it makes sense to
standardize on a way to provide multiple arguments.  The stack
approach seems to be a good comprommise.

So let's start with that: tuple <-> stack conversion.

  liftStack1 f (a,s) = (f a, s)
  liftStack2 f (a,(b,s)) = (f a b, s)
  liftStack3 f (a,(b,(c,s))) = (f a b c, s)

The problem with those is that they only work for functions.  To make
these compatible with Arrows we need to stick to something that's
accessible through tupling.  Wait... it's always possible to lift
plumbing functions so this is really not a big deal.  Things do need
to be uncurried though, so these look better: