Arrows first encounter

UPDATE: My post appeared on Reddit's programming feed. Thank you! Also, my post's title should've been "Point-free programming style first encounter", but I'm too lazy to change it ^_^

I was really busy lately so no post around for a while. Surprisingly, I wasn't busy wrinting code but actually thinking about the problem: this is feasible in Haskell as the code is more concise and the typing system keeps you from doing stupid design mistakes (or at least make them appear earlier than in other programming language).

Now, done with the ritual Haskell-awe prologue, here my post for today.

Lately, I've been working to a program manipulating objects which turned out to be monomials, which I represented as a pair of (Double,[Int]), i.e.:

(4.0,[1,2,-1,-2]) -> 4.0 x(1,1) x(2,2) x(3,-1) x(4,-2)

where x(i,j) are unknowns indexed by a pair. Since I assume that the first component of the unknowns' pairs will be the sequence 1,2,3,... I only need to specify the second component. I know, it's kinda weird, but it has to do with my domain problem which is related to finite difference operators for PDE.

Now I want to define a "product" operator which works like this:

(k,[b,c,d]) * (h,[e,f,g]) = (k*h,[a+e, c+f, d+g])

I can define this like follows:

prod (k,ll) (h,rl) = (k*h, zipWith (+) ll rl)

This is perfectly correct and good as it's very expressive.

Now, I want to apply the same function monadically to list arguments, i.e.:

prod :: [(Double,[Int])] -> [(Double,[(Double,[Int])] -> [(Double,[Int])]

To do this, I'll use liftM2 which take a function of two arguments and applies it to every pair formed taking an element from the first list and an element from the second. So:

prodM = liftM2 prod

But I'll never use prod by itself, so let's put this in a lambda abstraction and rename prodM to prod:

prod = liftM2 $ \(k,ll) (h,rl) -> (k*h, zipWith (+) ll rl)

Again, this is correct but my Haskell soul is becoming more strict and such a formulation sounds bad to me (I could've felt perfectly right with some month ago). I don't like lambdas when used this way, I see as an intrusive element in the perfect world of function combinators/operators (and liftM2 is such a combinator). More, I had to specify that prod requires two tuples while it'd be neat if the compiler could infere this automatically: I see this as code replication issue.

The solution to this dilemma is using point-free style programming. I'll abuse arrow combinators a bit. Specifically, there's the (***) operator which takes two function f and g and applies them to a tuple:

(f *** g) (a,b) = (f a, g b)

What if I need to combine two tuples using two separate binary operators? I.e.:

(f ***' g) (a,b) (c,d) = (f a c, g b d)

Arrows module doesn't provides such a combinator but we could build one. First, if we combine f and g using (***), we get a pair of two functions as f and g are partially evaluated. What we need now is to interpose (***) between these two functions. How to do this? Simple, we just need to uncurry (***). So, now:

(f ***' g) = uncurry (***) . (f *** g)

and we're done as f ***' g returns a function taking two tuples and apply f and g separately to each component. This is good as we can rewrite prod as:

prod = liftM2 $ uncurry (***) . ((*) *** (zipWith (+)))

which is essentially a smart combination of functions. Notice that no arguments of prod has been specified: this is where point-free programming style really lies. Changing the way prod is written will change the type of its arguments, in single place, without requiring you to rewrite them in two places (i.e. the argument list).