What is a general scheme for writing a function in pointfree style?

Question

I am working through the 20 Intermediate Haskell Exercises at the moment, which is quite a fun exercise. It involves implementing various instances of the typeclasses Functor and Monad (and functions that takes Functors and Monads as arguments) but with cute names like Furry and Misty to disguise what we're doing (makes for some interesting code).

I've been trying to do some of this in a point-free style, and I wondered if there's a general scheme for turning a point-ful (?) definition into a point-free definition. For example, here is the typeclass for Misty:

class Misty m where
  unicorn :: a -> m a
  banana :: (a -> m b) -> m a -> m b

(the functions unicorn and banana are return and >>=, in case it's not obvious) and here's my implementation of apple (equivalent to flip ap):

apple :: (Misty m) => m a -> m (a -> b) -> m b
apple x f = banana (\g -> banana (unicorn . g) x) f

Later parts of the exercises have you implement versions of liftM, liftM2 etc. Here are my solutions:

appleTurnover :: (Misty m) => m (a -> b) -> m a -> m b
appleTurnover = flip apple

banana1 :: (Misty m) => (a -> b) -> m a -> m b
banana1 =  appleTurnover . unicorn

banana2 :: (Misty m) => (a -> b -> c) -> m a -> m b -> m c
banana2 f = appleTurnover . banana1 f

banana3 :: (Misty m) => (a -> b -> c -> d) -> m a -> m b -> m c -> m d
banana3 f x = appleTurnover . banana2 f x

banana4 :: (Misty m) => (a -> b -> c -> d -> e) -> m a -> m b -> m c -> m d -> m e
banana4 f x y = appleTurnover . banana3 f x y

Now, banana1 (equivalent to liftM or fmap) I was able to implement in pointfree style, by a suitable definition of appleTurnover. But with the other three functions I've had to use parameters.

My question is: is there a recipe for turning definitions like these into point-free definitions?

Answer 1

As demonstrated by the pointfree utility, it's possible to do any such conversion automatically. However, the result is more often obfuscated than improved. If one's goal is to enhance legibility rather than destroy it, then the first goal should be to identify why an expression has a particular structure, find a suitable abstraction, and build things up that way.

The simplest structure is simply chaining things together in a linear pipeline, which is plain function composition. This gets us pretty far just on its own, but as you noticed it doesn't handle everything.

One generalization is to functions with additional arguments, which can be built up incrementally. Here's one example: Define onResult = (. (.)). Now, applying onResult n times to an initial value of id gives you function composition with the result of an n-ary function. So we can define comp2 = onResult (.), and then write comp2 not (&&) to define a NAND operation.

Another generalization--which encompasses the above, really--is to define operators that apply a function to a component of a larger value. An example here would be first and second in Control.Arrow, which work on 2-tuples. Conal Elliott's Semantic Editor Combinators are based on this approach.

A slightly different case is when you have a multi-argument function on some type b, and a function a -> b, and need to combine them into a multi-argument function using a. For the common case of 2-ary functions, the module Data.Function provides the on combinator, which you can use to write expressions like compare `on` fst to compare 2-tuples on their first elements.

It's a trickier issue when a single argument is used more than once, but there are meaningful recurring patterns here that can also be extracted. A common case here is applying multiple functions to a single argument, then collecting the results with another function. This happens to correspond to the Applicative instance for functions, which lets us write expressions like (&&) <$> (> 3) <*> (< 9) to check if a number falls in a given range.

The important thing, if you want to use any of this in actual code, is to think about what the expression means and how that's reflected in the structure. If you do that, and then refactor it into pointfree style using meaningful combinators, you'll often make the intent of the code clearer than it would otherwise be, unlike the typical output of pointfree.

Answer 2

Yes! One of the tricks is to write your dots in prefix notation rather than infix. Then you should be able to find new things that look like function composition. Here's an example:

banana2 f = appleTurnover . banana1 f
          = (.) appleTurnover (banana1 f)
          = ((.) appleTurnOver) . banana1 $ f
banana2 = (appleTurnover .) . banana1

The source code for the pointfree utility contains more, but this one handles a lot of cases.

banana4 f x y = appleTurnover . banana3 f x y
              = (.) appleTurnover ((banana3 f x) y)
              = ((.) appleTurnover) . (banana3 f x) $ y
banana4 f x = ((.) appleTurnover) . (banana3 f x)
            = (.) ((.) appleTurnover) (banana3 f x)
            = ((.) ((.) appleTurnover)) ((banana3 f) x)
            = ((.) ((.) appleTurnover)) . (banana3 f) $ x
banana4 f = ((.) ((.) appleTurnover)) . (banana3 f)
          = (.) ((.) ((.) appleTurnover)) (banana3 f)
          = ((.) ((.) ((.) appleTurnover))) (banana3 f)
          = ((.) ((.) ((.) appleTurnover))) . banana3 $ f
banana4 = ((.) ((.) ((.) appleTurnover))) . banana3
        = (((appleTurnover .) .) .) . banana3

Answer 3

I use the following term rewrite system:

\x -> f x ------> f 
f y x ----------> flip f x y
\x -> f (g x) --> f . g

It is incomplete (read why in books about combinatory logic), but it's enough:

Here is banana2:

banana2 f = appleTurnover . banana1 f

Rewrite as a lambda:

banana2 = \f -> appleTurnover . banana1 f

Write (.) in prefix style:

banana2 = \f -> (.) appleTurnover (banana1 f)

Note that

banana2 = \f -> ((.) appleTurnover) (banana1 f)

So rule 3 can be applied. f is (.) appleTurnover and g is banana:

banana2 = ((.) appleTurnover) . banana1

Answer 4

There is a pointfree package which takes a Haskell function definition and attempts to re-write it in a pointfree style. I'd suggest experimenting with it to get new ideas. See this page for more details; the package is available here.

Answer 5

Since pointfree style is combinators style, just apply known combinators definitions, reading them backwards to make the substitution:

B f g x = f (g x)     -- (.) , <$> for ((->) a)
C f x y = f y x       -- flip
K x y = x             -- const
I x = x               -- id
S f g x = f x (g x)   -- <*> , ap  for ((->) a)
W f x = f x x         -- join
(f >>= g) x = g (f x) x
(f =<< g) x = f (g x) x

At times liftMx, liftAx, sequence, sequenceA can simplify things. I'd also consider foldr, unfoldr, iterate, until etc. as basic combinators.

Often, using operator sections helps too:

op a b = (a `op` b) = (`op` b) a = (a `op`) b

Some patterns can become familiar and so, used directly:

((f .) . g) x y = f (g x y)
((. f) . g) x y = g x (f y)

(((f .) .) . g) x y z = (f .) (g x y) z = f (g x y z)
(((. f) .) . g) x y z = (. f) (g x y) z = g x y (f z)

etc.