Arrows

HXML Filters are an instance of the Arrow class.

Arrows are much easier to use than to explain. See <URL:http://www.soi.city.ac.uk/~ross/arrows/> for a longer discussion of arrows (but note that the HXML implementation uses a different notation for many of the combinators).

class Arrow a where
    (>>>) ::  a b c -> a c d -> a b c
    arr   ::  (b -> c) -> a b c

Basically, the Arrow type class represents a computation that takes inputs of some type b and produces outputs of some other type c. Several combinators are available to glue together arrows. The >>> operator composes two arrows in sequence: if f :: Filter a b and g :: Filter b c, then f >>> g :: Filter a c passes the output of f to the input of g.

The arr combinator turns an ordinary function f :: b -> c into an arrow arr f :: a b c. aConst constructs a constant arrow, which always outputs a specified value: aConst x = arr (const x).

The simplest kind of Arrows are ordinary functions: here >>> is just function composition (with the arguments in the opposite order from usual), and arr is the identity:

instance Arrow (->) where
    f >>> g	= \x -> g (f x)
    arr f	= f

Any Monad m can be made into a monadic arrow MA m (also called a Kleisli arrow).

newtype MA m a b = MA (a -> m b)
instance Monad m => Arrow (MA m) where
    arr f 		= MA (return . f)
    MA f >>> MA g	= MA (\b -> f b >>= g)

HXML Filters are another kind of arrow: here composing two arrows f and g applies f to an input to produce a list of intermediate results, applies g to each intermediate result, and concatenates the output of g to produce the final result. Filters are equivalent to monadic arrows over the List monad, MA [], though the implementation is slightly different.

instance Arrow Filter where
    arr f = Filter (\x -> [f x])
    (Filter f) >>> (Filter g)
	= Filter (\x -> [z | y <- f x, z <- g y])
	= Filter (concatMap f g)

The +++ operator applies two filters to the same input and concatenates their result:

class ArrowPlus a where
    (+++) :: a b c  -> a b c -> a b c
instance ArrowPlus Filter where
    (Filter f) +++ (Filter g) = Filter (\x -> f x ++ g x)

Combining arrows: product combinators

class Arrow a where
	(&&&)	:: a b c -> a b d -> a b (c,d)
	(>&<)	:: a b c -> a d e -> a (b,d) (c,e)
	apfst	:: a b c -> a (b,x) (c,x)
	apsnd	:: a b c -> a (x,b) (x,c)

The &&& operator is a Cartesian product combinator: f &&& g passes its input to both f and g, and combines the results. >&< combines two arrows in a different way: f >&< g takes a pair as input, passes the first element to f, the second element to g and combines the results. Finally, apfst and apsnd apply a process to the first (resp. second) member of their input and pass the other on unchanged.

This is probably best understood by looking at the instance definitions for function and filter arrows:

instance Arrow (->) where
	f &&& g 	= \b     -> (f b, g b)
	f >&< g		= \(b,d) -> (f b, g d)
	apfst f (b,c)	= (f b,c)
	apsnd g (b,c)	= (b,g c)
instance Arrow Filter where
	(Filter f) &&& (Filter g)
		= Filter $ \b     -> [(c,d) | c <- f b, d <- g b]
	(Filter f) >&< (Filter g)
		= Filter $ \(b,d) -> [(c,e) | c <- f b, e <- g d]

Adding guards: class ArrowZero

An ArrowZero is a kind of arrow that has a natural ``zero'', ``failure'', or ``nothing'' operation, aZero. For Filter, this is (the arrow that always returns) the empty list. ArrowZero also supports guards, which pass inputs which satisfy some predicate through unchanged; those which fail the test are mapped to the zero element. The aMaybe arrow is a convenience routine that ``unwraps'' a Maybe input, mapping Just x to x and Nothing to the zero element.

class (Arrow a) => ArrowZero a where
	aZero  :: a b c
	aGuard :: (b -> Bool) -> a b b
	aMaybe :: a (Maybe c) c

Adding conditionals: class ArrowChoice

The ArrowChoice class enhances arrows with conditional expressions, using the standard Haskell disjoint union type Either:

class (Arrow a) => ArrowChoice a where
	(|||)	:: a b c -> a d c -> a (Either b d) c
	(>|<)	:: a b c -> a d e -> a (Either b d) (Either c e)
	apl	:: a b c -> a (Either b d) (Either c d)
	apr	:: a b c -> a (Either d b) (Either d c)
	-- ...

instance ArrowChoice (->) where
    f (|||) g	= \x -> case x of Left b -> f b ; Right d -> g d
    f (>|<) g	= (Left . f) ||| (Right . g)
    apl f 	= f  >|< id
    apr g 	= id >|< g

The sum combinators |||, >|<, apl, and apr are dual to the product combinators &&&, >&<, apfst, and apsnd.

There is also an if-then-else construct analogous to C's ternary ... ? ... : ... operator:

data Choice a = a :> a
class (Arrow a) => ArrowChoice a where
    ( ?>) :: (b -> Bool) -> Choice (a b c) -> a b c
    (>?>) :: a b Bool    -> Choice (a b c) -> a b c

instance ArrowChoice (->) where
    p ?> f :> g	= \x -> if p x then f x else g x

If p is a predicate p :: b -> Bool and f and g are arrows f, g :: Arrow b c, then p ?> f :> g passes its input to one of f or g depending on the result of p. For the >?> combinator, the condition is also an arrow p :: Arrow b Bool.