Reverse Function Composition in Haskell

Question

Consider the following Haskell code:

countWhere :: (a -> Bool) -> [a] -> Int
countWhere predicate xs = length . filter predicate $ xs

In JavaScript this would be written as follows:

function countWhere(predicate, xs) {
    return xs.filter(predicate).length;
}

As you can see, function composition is very similar to chaining methods in JavaScript. I really like the way chaining methods reads from left to right. In Haskell I can do something similar using the >>> function from Control.Arrow and reverse function application as follows:

import Control.Arrow

($>) :: a -> (a -> b) -> b
($>) = flip ($)

countWhere :: (a -> Bool) -> [a] -> Int
countWhere predicate xs = xs $> filter predicate >>> length

Now I want to write this function in point free style. Using function composition I would write it as follows:

(.:) :: (b -> c) -> (d -> a -> b) -> d -> a -> c
(.:) = (.) (.) (.)

countWhere ::  (a -> Bool) -> [a] -> Int
countWhere = length .: filter

However I would like to write this function in point free style using reverse function composition as follows:

(.:) :: (b -> c) -> (d -> a -> b) -> d -> a -> c
(.:) = (.) (.) (.)

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

countWhere :: (a -> Bool) -> [a] -> Int
countWhere = filter :. length

My gripe is that I have to define the :. function in terms of function composition instead of reverse function composition. That is:

(:.) = flip $ (.) (.) (.)

-- instead of

(:.) = (>>>) (>>>) (>>>)

Of course (>>>) (>>>) (>>>) is of the wrong type. It's not the function that I am looking for.

The beauty of function composition is that it can be composed with itself to form "higher order function compositions" as demonstrated above. Hence although its type signature is intuitively backwards it's actually forward, which explains why f . g = \x -> f (g x) instead of f . g = \x -> g (f x).

This brings me to my actual question: is there any way to define "higher order reverse function compositions" in terms of reverse function composition (i.e. >>>) instead of fliping the corresponding "higher order function compositions"?

I'm looking for an answer that has its roots in either Category Theory or other branches of Mathematics.

flip is nothing to be ashamed of. The definition of (.:) happens not to use it -- but it's not really a deep observation about category theory; more like a coincidence. — Daniel Wagner

Daniel Gratzer Daniel Gratzer · Accepted Answer · 2013-11-23T05:02:56

So here's a pseudo pointfree answer

(.:.) :: (a -> b -> c) -> (c -> d) -> a -> b -> d
f .:. g = (,) f >>> app >>> (>>> g)

This relies on what are called "exponentials" in category theory. Expontentials basically provide two functions

curry :: ((a, b) -> c, a) -> c^b
eval  :: (c^b, b)         -> c

Which is more or less a general version of curry and uncurry ($).

This can be converted to pointfree (by pointfree)

(.:.) = (. flip (>>>)) . (>>>) . (>>> app) . (,)
(.:.) = (,) >>> fmap app >>> (>>>) >>> ((<<<) >>>)

Which is well, hideous. The other option is to use curry and uncurry. Curry and uncurry essential witness the isomorphism between exponentials and arrows: Hom((a, b), c) ~~ Hom(a, c^b).in Hask.

(.:.) = uncurry >>> (>>>) >>> (>>>curry)

Reverse Function Composition in Haskell

1 Answers