Pointfree

Pointfree Style

It is very common for functional programmers to write functions as a composition of other functions, never mentioning the actual arguments they will be applied to. For example, compare:

sum = foldr (+) 0

with:

sum' xs = foldr (+) 0 xs

These functions perform the same operation, however, the former is more compact, and is considered cleaner. This is closely related to function pipelines: it is clearer to write let fn = f . g . h than to write let fn x = f (g (h x)).

This style is particularly useful when deriving efficient programs by calculation, but it is good discipline in general. It helps the writer (and reader) think about composing functions (high level), rather than shuffling data (low level).

It is a common experience when rewriting expressions in pointfree style to derive more compact, clearer versions of the code -- explicit points often obscure the underlying algorithm.

Point-free map fusion:

foldr f e . map g == foldr (f.g) e

versus pointfull map fusion:

foldr f e . map g == foldr f' e
     where f' a b = f (g a) b

Some more examples:

-- point-wise, and point-free member
mem, mem' :: Eq a => a -> [a] -> Bool

mem x lst = any (== x) lst
mem'      = any . (==)

But pointfree has more points!

A common misconception is that the `points' of pointfree style are the (.) operator (function composition, as an ascii symbol), which uses the same identifier as the decimal point. This is wrong. The `point' in point-free style refers instead to function arguments, or named variables. In pointfree style you name no variables.

Background

To find out more about this style, search for Squiggol and the Bird-Meertens Formalism, a style of functional programming by calculation that was developed by Richard Bird, Lambert Meertens, and others at Oxford University. Jeremy Gibbons has also written a number of papers about the topic, which are cited below.

Tool Support

Thomas Yaeger has written a Lambdabot plugin to automatically convert a large subset of Haskell expressions to pointfree form. This tool has made it easier to use the more abstract pointfree encodings (as it saves some mental gymnastics on the part of the programmer). You can experiment with this in the haskell IRC channel.

The @pl (point-less) plugin is rather infamous for using the (-> a) monad to obtain concise code. It also makes use of Arrows. It also sometimes produces (amusing) code blows ups with the (.) operator.

A transcript:

> @pl \x y -> x y
id

> @pl \x y -> x + 1
const . (1 +)

> @pl \v1 v2 -> sum (zipWith (*) v1 v2)
(sum .) . zipWith (*)

> @pl \x y z -> f (g x y z)
((f .) .) . g

> @pl \x y z -> f (g x y) z
(f .) . g

> @pl \x y z -> f z (g x y)
(flip f .) . g

> @pl \(a,b) -> (b,a)
uncurry (flip (,))

> @pl f a b = b a
f = flip id

> @pl \ x -> x * x
join (*)
   
> @pl \a b -> a:b:[]
(. return) . (:)

> @pl \x -> x+x+x
(+) =<< join (+)

> @pl \a b -> Nothing
const (const Nothing)

> @pl \(a,b) -> (f a, g b)
f *** g

> @pl \f g h x -> f x `h` g x
flip . (ap .) . flip (.)

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

> @pl \f xs -> xs >>= return . f
fmap

> @pl \h f g x -> f x `h` g x
liftM2

> @pl \f a b c d -> f b c d a
flip . ((flip . (flip .)) .)

> @pl \a (b,c) -> a c b
(`ap` snd) . (. fst) . flip

> @pl \x y -> compare (f x) (f y)
((. f) . compare .)

For many many more examples, google for the results of '@pl' in the haskell logs. It can, of course, get out of hand:

> @pl \(a,b) -> a:b:[]
uncurry ((. return) . (:))

> @pl \a b c -> a*b+2+c
((+) .) . flip flip 2 . ((+) .) . (*)

> @pl \f (a,b) -> (f a, f b)
(`ap` snd) . (. fst) . (flip =<< (((.) . (,)) .))

> @pl \f g (a,b) -> (f a, g b)
flip flip snd . (ap .) . flip flip fst . ((.) .) . flip . (((.) . (,)) .)

Obfuscation

Point-free style can (clearly) lead to Obfuscation when used unwisely. As higher-order functions are chained together, it can become harder to mentally infer the types of expressions. The mental cues to an expressions type (explcit function arguments, and the number of arguments) go missing.

Perhaps this is why pointfree style is sometimes (often?) referred to as pointless style.

References

One early reference is

* Backus, J. 1978. "Can Programming Be Liberated from the von Neumann Style? 
A Functional Style and Its Algebra of Programs," Communications of the 
Association for Computing Machinery 21:613-641.

which appears to be available (as a scan) at http://www.stanford.edu/class/cs242/readings/backus.pdf

A paper specifically about point-free style:

* http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#radix

This style underlies a lot of expert Haskeller's intuitions. A rather infamous paper (for all the cute symbols) is Erik Meijer et. al's:

* Functional Programming with Bananas, Lenses, and Barbed Wire, http://wwwhome.cs.utwente.nl/~fokkinga/mmf91m.ps.

Squiggol, and the Bird-Meertens Formalism:

* http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#squiggolintro.
* A Calculus of Functions for Program Derivation, R.S. Bird, in Res Topics in Fnl Prog, D. Turner ed, A-W 1990.
* The Squiggolist, ed Johan Jeuring, published irregularly by CWI Amsterdam.