A Lazy Sequence

Functions of functions

The following is some theoretical learning I have done about functions of functions in Haskell and F#. It uses haskells type and function notation but has a couple of F#s (perhaps actually ocaml?) names for functions because they are clearer for my purposes because they have clear directionality, and the flipped versions show some of the similar properties more clearly than the commonly used versions.

There are two main operations you can do with function values: Apply them, and compose them. One other operation referenced here is flip, which swaps the argument order of the function.

First up, the function application operator, with its haskell name and then the F# versions that i'm going to prefer:

$  :: (a -> b) -> a -> b
<| :: (a -> b) -> a -> b  -- Function application; 
<| = ($)
|> :: a -> (a -> b) -> b  -- Pipeline
|> = flip ($)

The second common operator on functions is function composition; Again the haskell name followed by the F# names. The latter is not to be confused with haskell's monad operator of the same name <<.

.  :: (b -> c) -> (a -> b) -> (a -> c)
<< :: (b -> c) -> (a -> b) -> (a -> c)
<< = (.)
>> :: (a -> b) -> (b -> c) -> (a -> c) 
>> = flip (.)

In Haskell its not immediately obvious that monadic bind is related to function application; in this case apply a function to a value in a monadic context. With the flipped function application (aka pipeline) operator we can see clear similarities in the types:

|>  :: a -> (a -> b) -> b 
>>= :: Monad m => m a -> (a -> m b) -> m b 
<|  :: (a -> b) -> a -> b
=<< :: Monad m => (a -> m b) -> m a  -> m b

Note that in both cases there is a function applied to a value, in the case of the bind operators that value is in a Monad type. The difference is that bind has a more specific type than plain application, in the form of a type that implements the monad interface. This provides richer semantics about the function application.

We know that there is a relationship between function application and function composition. This is particularly clear with pipeline and right facing compose. In this expression, g and h are both functions.

f val = val |> g |> h == f = g >> h

And given we know there is a relationship between bind and application, it can easily be supposed that there is a similar operation to composition specifically for monadic functions.

If we replace the three functions in the type of compose with monadic operations, we get an operator with a type such as:

>>  :: (a -> b) -> (b -> c) -> (a -> c) 
>=> :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
<<  :: (b -> c) -> (a -> b) -> (a -> c) 
<=< :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)

Indeed this operator does exist and is known as Kleisli composition of monads.

Generalized functions of functions

A key feature that Monads bring is that they allow a single operator to generalize many different kinds of function applications. The types that implement the Monad typeclass in haskell each provide different contexts to manage how various functions are applied. The identity monad effectively is the function application operator dressed up with a more complex type.

Given there is a generalization for application, it seems likely that there would be a generalisation for composition too as we have already seen two general patterns. It turns out that there is, and in Haskell it is known as the Arrow typeclass. Of particular interest here, Arrow provides an operator:

>>> :: Arrow ar => ar b c -> ar c d -> ar b d 

An arrow type 'ar a b' represents a transformation from some type a to type b. For example:

a -> b -- becomes:
Arrow ar => ar a b
Monad m => a -> m b -- becomes:
(Arrow ar, Monad m) => ar a (m b)

This, the function application (>>) and Kleisli operators (>=>) can be represented in terms of Arrows as:

>>  :: (a -> b) -> (b -> c) -> (a -> c) 
>>> :: Arrow ar => ar b c -> ar c d -> ar b d
>=> :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
>>> :: (Arrow ar, Monad m) => ar b (m c) -> ar c (m d) -> ar b (m d)

What's the point?

All this shows just shows a correspondence between monads, arrows and the primative operations of functions. In particular how those operations can be generalised when more specific types are involved.

23 October 2009