Reasonig about combinators (a lambda-calculus puzzle on composing compositions)

In Haskell, \f -> \g -> (((f.).).) g is equivalent to \x y z -> f (g x y z), and more generally, \f -> \g -> (((f.)... .) g with n compositions is equivalent to x1 ... xn -> f (g x1 ... xn) with n arguments.

But what is \f -> \g -> (.(.(.f))) g? Can you generalize?

What about arbitrary left and right compositions, like (.(.((.f).)))? Can a general description be given?

I am interested in your strategies in tackling such questions. I find reasoning about combinators quickly overwhelming. Sure, I can mechanically reduce a lambda term to normal form, but it's usually not that insightful. Is the key once more abstraction, through understanding of combinators at a high operational level?

Any pointers to resources for reasoning about combinators would be appreciated.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

A bit of light...

Abstraction is the key, at least somewhat. I also find sections of (.) very difficult to comprehend, but some better names make things a little clearer.

result = (.)
argument = flip (.)

The insight is that (.) transforms a function to operate on the result of another function, while flip (.) transforms a function to operate on the argument of another function. Since all functions are curried, chains of these two transformations cover all the possibilities. Your first example:

(((f.).).) g
  == (result.result.result) f g 
  == \x y z -> f (g x y z)

Your second example:

(.(.(.f))) g
  == (argument.argument.argument) f g
  == \ a -> g (\ b -> a (\ c -> b ((+) c))) -- or something?

If f is a function a -> b, then (argument.argument.argument) f will transform a function g of type:

(((b -> c2) -> c1) -> c)

into a function of type:

(((a -> c2) -> c1) -> c)

In English, it will apply f to the argument of the argument of the argument of g.

Of course, that's not as useful as the first example, because while multi-argument curried functions are common, functions (like this second g) that expect arguments with types like (((a -> b) -> c) -> d) are less so.

In general, chains of "argument" aren't so common, but it's very common to see chains like "argument.result.result.result", which will apply a function to the 4th (curried) argument of another function.

Here are a few blog posts to get you started, one from me and a couple from Conal Elliott: 1, 2. Point-free style can be comprehensible and useful when you work with the right tools, but obfuscation is obfuscation in any language...


This is probably only barely on-topic for LtU... Probably you should pursue it further in a Haskell-specific forum...


Sorry for the drift. But thanks again for taking the time to reply.


I figured it out a bit by trial and error by reasoning on the types of the combinators, but your explanation in terms of argument and result is very insightful.