Reverse Function Composition in Haskell
category-theory, function-composition, haskell
Solution
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)
Problem
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 `flip`ing 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.