> module Week1403_1 where
> import Control.Monad

* The Arrow class

Generalizing this development leads to the arrow class.

> class Arrow0 arr where
>   arr :: (a -> b) -> arr a b
>   (>>>) :: arr a b -> arr b c -> arr a c

> instance Arrow0 (->) where
>   arr f = f
>   f >>> g = g . f

A trivial arrow instance: functions.

 > instance Arrow0 (->) where
 >   arr = id
 >   (>>>) = flip (.)

To make Kleisli arrows an instance, they need to be made a newtype.

> newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b }

> instance (Functor m, Monad m) => Arrow0 (Kleisli m) where
>   arr f = Kleisli (return . f)
>   f >>> g = Kleisli (join . fmap (runKleisli g) . runKleisli f)

The counter may now be programmed.

> countA w = Kleisli readFile >>>
>            arr words >>> arr (filter (==w)) >>> arr length >>>
>            Kleisli print

> runcount w filename = runKleisli (countA w) filename

Another instance.

Stream transformers model discrete time varying behavior.

> newtype SF a b = SF { runSF :: [a] -> [b] }

> instance Arrow0 SF where
>   arr f = SF (map f)
>   f >>> g = SF (runSF f >>> runSF g)


Arrow types are mostly useful for the additional operations that they support.

> delay x = SF (x:)

Another instance.

State and behavior transformers.

> newtype SB s a b = SB { runSB :: (s -> a) -> (s -> b) }

> instance Arrow0 (SB s) where
>   arr f = SB (f .)
>   f >>> g = SB (runSB f >>> runSB g)

f :: a -> b
(s -> a) -> (s -> b)


* Laws

In analogy to the monad laws, there are also arrow laws.
However, there are twenty of them stated in the original paper and
another seven laws in a followup paper. A recent paper ("The arrow
calculus" by Phil Wadler and others) brings this down to a much
smaller number. But it would require learning the arrow calculus.

* Arrows and pairs

The arrow interface introduced up to now cannot handle passing
multiple arguments to a function. With a monad it is quite
straightforward to compute to numbers and multiply them:

> mulM :: Monad m => m Int -> m Int -> m Int
> mulM a b = do { x <- a; y <- b; return (x * y) }

But if we want to do the same with arrows, we fail:

> mulA0 :: Arrow0 arr => arr a Int -> arr a Int -> arr a Int
> mulA0 f g = undefined

It's unclear how to compose f and g: f consumes the input a and yields
an Int. But then, the >>> operator requires an arrow with output a to
compose with g. So a further operation is needed to `pair up' two
arrows.

> class Arrow0 arr => Arrow1 arr where
>   (&&&) :: arr a b -> arr a c -> arr a (b,c)

> mulA :: Arrow1 arr => arr a Int -> arr a Int -> arr a Int
> mulA f g = f &&& g >>> arr (uncurry (*))

We need to extend the existing instances...

> instance Arrow1 (->) where
>   f &&& g = \a -> (f a, g a)

> instance (Monad m, Functor m) => Arrow1 (Kleisli m) where
>   f &&& g = Kleisli (\a -> do b <- runKleisli f a
>                               c <- runKleisli g a
>                               return (b,c))

f :: a -> m b
g :: a -> m c
a -> m (b,c)


> instance Arrow1 SF where
>   f &&& g = SF ((runSF f &&& runSF g) >>> uncurry zip)

first parenthesis :: ([b], [c])
wanted :: [(b, c)]

An example of a stream function.

> pairPred = arr id &&& delay 0

A simpler way to make arrows and pairs interact.

> (***) :: Arrow arr => arr a b -> arr c d -> arr (a,c) (b,d)


> class Arrow1 arr => Arrow arr where
>   first :: arr a b -> arr (a,c) (b,c)

We can define second that works on the second component from first:

> second :: Arrow arr => arr a b -> arr (c,a) (c,b)
> second f = arr swap >>> first f >>> arr swap

> swap (x,y) = (y,x)

Now (***) becomes defineable:

> f *** g = first f >>> second g

We can express &&& in terms of ***:

> diag :: Arrow arr => arr a (a,a)
> diag = arr (\x -> (x,x))

> f &&&& g = diag >>> (f *** g)

> instance Arrow (->) where
>   first f = \(a,c) -> (f a,c)


> instance (Functor m, Monad m) => Arrow (Kleisli m) where
>   first f = Kleisli (\(a, c) -> do { b <- runKleisli f a; return (b,c)})

> instance Arrow SF where
>   first f = SF (unzip >>> first (runSF f) >>> uncurry zip)

f :: [a] -> [b]
first f :: [(a,c)] -> [(b,c)]


* Arrows and conditionals

So far, arrows do not interact well with conditionals. To build an
arrow that depends on the result of a previous arrow requires further
combinators. Such a combinator might look like this:

> ite :: ArrowChoice arr => arr a Bool -> arr a b -> arr a b -> arr a b

However, its implementation may be built from simpler parts.

> ite p f g = (p &&& arr id) >>> arr isoBoolA >>> (f ||| g)

The bool type is too specific.

> isoBoolA :: (Bool, a) -> Either a a
> isoBoolA (True, a) = Left a
> isoBoolA (False, a) = Right a

The choice operator, version 1.

> (|||) :: ArrowChoice arr => arr a c -> arr b c -> arr (Either a b) c

This signature is dual to (&&&)'s type.
Let's explore duality further and find the dual to (***) and first
and make them part of the definition of an extended arrow class:

> (+++) :: ArrowChoice arr => arr a b -> arr c d -> arr (Either a c) (Either b d)

The first choice operator becomes defineable:

> f ||| g = f +++ g >>> arr (either id id)

But again, there is a simpler combinator underlying (+++) that becomes
the basis of the extended type class.

> class Arrow arr => ArrowChoice arr where
>   left :: arr a b -> arr (Either a c) (Either b c)

Its mirror image is easily definable.

> right :: ArrowChoice arr => arr a b -> arr (Either c a) (Either c b)
> right f = arr mirror >>> left f >>> arr mirror

> mirror (Left x) = Right x
> mirror (Right y) = Left y

And we can complete the definition for the second choice operator.

> f +++ g = left f >>> right g

It remains to implement instances of ArrowChoice for the examples.

> instance ArrowChoice (->) where
>   left f = either (Left . f) Right -- Either a c



For stream functions, we need to restrict to length preserving
functions.

* Synchronous circuits

A nor-gate

> nor :: SF (Bool, Bool) Bool
> nor = arr (not . uncurry (||))

Rising edge detection: compare the signal with a one-step-delayed copy

> edge :: SF Bool Bool
> edge = arr id &&& delay False >>> arr detect
>   where detect (a,b) = a && not b

It is well-known that connecting nor-gates suitably results in a
flip-flop. To represent that, we need to feed back the result of one
arrow into its own input. A new combinator is required for this task.

> class Arrow arr => ArrowLoop arr where
>   loop :: arr (a,c) (b,c) -> arr a b

> instance ArrowLoop (->) where
>   loop f a = b
>     where (b,c) = f (a,c)

What about the instances for Kleisli and stream functions?