Pointless fun

At the end of my last post, I posed a question: can we write combinators that allow us to write something like this:

argument length . (result.argument) length $ compare

more like this:

compare <$> length <*> length

(Of course, we aren't really looking for an instance of Applicative, so the actual combinators will be different. But you see the idea...)

After a bit of thought, I've found that we can solve this pretty easily. I suspected that the solution would involve type classes, but it doesn't. If we compromise (or generalize) and add a transformer for the result type as well, we can define ($.) and (~>) so that we can write:

compare $. length ~> length ~> id

Implementation follows...

Recall that the above is a point-free version of

\x y -> compare (length x) (length y)

In effect, we want to be able to apply a curried function to "argument transformers" rather than directly to arguments. In other words, we want to go from

foo :: a -> b -> c

to

foo' :: (a' -> a) -> (b' -> b) -> c

As I said, we'll make one compromise, which is actually a generalization. We'll allow ourselves to transform the result type as well, leaving us with something like

foo'' :: (a' -> a) -> (b' -> b) -> (c' -> c)

We'll make use of two of Conal's combinators:

result = (.)
argument = flip (.)

but we'll also give them shorter names:

r = result
a = argument

The goal is to build up a chain like this:

f g     => a g $ f
f g h   => a g . (r.a) h $ f
f g h i => a g . (r.a) h . (r.r.a) i $ f

Ignore the fs for now. We rely on two facts: first, that result "distributes" across (.):

(r.a) h . (r.r.a) i == r (a h . (r.a) i)

and second, that result id does nothing:

result id f == id . f == f

So our chain is equivalent to:

a g . r id $ f
a g . r (a h . r id) $ f
a g . r (a h . r (a i . r id)) $ f

So our answer will use one combinator to build up the chain of transformations, and another to stick on the f, which we'd prefer to appear at the beginning.

Writing down the answer is pretty straightforward:

infixr 2 ~>
f ~> g = argument f . result g

infixl 1 $.
($.) = flip ($)

And now we can write:

compare $. length ~> length ~> id

The transformer to the right of ($.) looks like the type of the function to the left, and includes one operation to apply at each argument. id matches whatever is left (in this case, just the result).

A few things to notice:

  • Since these are curried functions, we only need to mention as many arguments as we like. id will take care of the rest. So we can write things like:
    compare $. length ~> id
  • The transformers can be as complex as we like:
    compare $. length ~> length.head ~> id
  • We can chain whole sequences, in the obvious way:
    compare $. length ~> length ~> id $. id ~> head ~> id

    which is of course equal to the above.

Is it useful? I'm not sure. There have been plenty of times when I've wanted it, but I've always found another way. Does it already exist? I'd love to know, and I'd also love to hear better names for ($.) and (~>)...

Tags:

Properties

Submitted by Luke Palmer on Fri, 02/19/2010 - 23:52.

I think (~>) is a pretty cool combinator. It generalizes to all Categories, of course. $. is left-to-right application, which I originally wanted but have, um, "grown out of"?

Anyway I just had fun proving (very directly) some interesting things which I hadn't taken the time to notice before:

argument f . result g = result g . argument f
(f ~> g) . (f' ~> g') = (f' . f) ~> (g . g')

So yeah, thanks for the discovery.