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

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)


(.(.(.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...

Incidentally

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

OK.

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

Thanks!

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.