Personal tools

Pointfree

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(and more)
(fmt)
Line 20: Line 20:
 
compact, and is considered cleaner. This is closely related to function
 
compact, and is considered cleaner. This is closely related to function
 
pipelines (and to [http://www.vex.net/~trebla/weblog/pointfree.html unix shell scripting]
 
pipelines (and to [http://www.vex.net/~trebla/weblog/pointfree.html unix shell scripting]
): it is clearer to write ''let fn = f . g . h'' than to
+
): it is clearer to write <hask>let fn = f . g . h</hask> than to
write ''let fn x = f (g (h x))''.
+
write <hask>let fn x = f (g (h x))</hask>.
   
 
This style is particularly useful when deriving efficient programs by
 
This style is particularly useful when deriving efficient programs by
Line 58: Line 58:
   
 
A common misconception is that the 'points' of pointfree style are the
 
A common misconception is that the 'points' of pointfree style are the
''(.)'' operator (function composition, as an ascii symbol), which
+
<hask>(.)</hask> operator (function composition, as an ascii symbol),
uses the same identifier as the decimal point. This is wrong. The term originated in topology, a branch of mathematics which works with spaces composed of points, and functions between those spaces. So a 'points-free' definition of a function is one which does not explicitly mention the points (values) of the space on which the function acts. In Haskell, our 'space' is some type, and 'points' are values. In the declaration:
+
which uses the same identifier as the decimal point. This is wrong. The
  +
term originated in topology, a branch of mathematics which works with
  +
spaces composed of points, and functions between those spaces. So a
  +
'points-free' definition of a function is one which does not explicitly
  +
mention the points (values) of the space on which the function acts. In
  +
Haskell, our 'space' is some type, and 'points' are values. In the
  +
declaration:
 
<haskell>
 
<haskell>
 
f x = x + 1
 
f x = x + 1
 
</haskell>
 
</haskell>
we define the function ''f'' in terms of its action on an arbitrary point ''x''. Contrast this with the points-free version:
+
we define the function <hask>f</hask> in terms of its action on an
  +
arbitrary point <hask>x</hask>. Contrast this with the points-free
  +
version:
 
<haskell>
 
<haskell>
 
f = (+ 1)
 
f = (+ 1)
Line 73: Line 73:
 
To find out more about this style, search for Squiggol and the
 
To find out more about this style, search for Squiggol and the
 
Bird-Meertens Formalism, a style of functional programming by
 
Bird-Meertens Formalism, a style of functional programming by
calculation that was developed by Richard Bird, Lambert Meertens, and
+
calculation that was developed by [http://web.comlab.ox.ac.uk/oucl/work/richard.bird/publications.html Richard Bird], [http://www.kestrel.edu/home/people/meertens/ Lambert Meertens], and
others at Oxford University. Jeremy Gibbons has also written a number of
+
others at Oxford University. [http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/ Jeremy Gibbons] has also written a number of
 
papers about the topic, which are cited below.
 
papers about the topic, which are cited below.
   
Line 85: Line 85:
 
pointfree form. This tool has made it easier to use the more abstract
 
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
 
pointfree encodings (as it saves some mental gymnastics on the part of
the programmer). You can experiment with this in the haskell IRC
+
the programmer). You can experiment with this in the [[IRC channel|Haskell IRC channel]].
channel.
 
   
The @pl (point-less) plugin is rather infamous for using the ''(-> a)''
+
The @pl (point-less) plugin is rather infamous for using the <hask>(-> a)</hask>
monad to obtain concise code. It also makes use of Arrows. It also
+
[[Monad|monad]] to obtain concise code. It also makes use of [[Arrow|Arrows]].
sometimes produces (amusing) code blow ups with the ''(.)'' operator.
+
It also sometimes produces (amusing) code blow ups with the
  +
<hask>(.)</hask> operator.
   
 
A transcript:
 
A transcript:
Line 155: Line 155:
 
</haskell>
 
</haskell>
   
For many many more examples, google for the results of '@pl' in the #haskell logs. (Or join #haskell on FreeNode and try it yourself!) It can, of course, get out of hand:
+
For many many more examples, google for the results of '@pl' in the
  +
[[IRC_channel|#haskell] logs. (Or join #haskell on FreeNode and try it
  +
yourself!) It can, of course, get out of hand:
   
 
<haskell>
 
<haskell>
Line 186: Line 186:
 
One early reference is
 
One early reference is
   
* Backus, J. 1978. "Can Programming Be Liberated from the von Neumann Style?
+
* 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.
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
 
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:
 
A paper specifically about point-free style:
* http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#radix
+
* http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#radix
   
 
This style underlies a lot of expert Haskeller's intuitions.
 
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:
 
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.
+
* Functional Programming with Bananas, Lenses, and Barbed Wire, http://wwwhome.cs.utwente.nl/~fokkinga/mmf91m.ps.
   
 
[http://en.wikipedia.org/wiki/Squiggol Squiggol], and the Bird-Meertens Formalism:
 
[http://en.wikipedia.org/wiki/Squiggol Squiggol], and the Bird-Meertens Formalism:
* http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#squiggolintro.
+
* 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.
+
* 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.
+
* The Squiggolist, ed Johan Jeuring, published irregularly by CWI Amsterdam.
   
 
[http://wiki.di.uminho.pt/wiki/bin/view/Alcino/PointlessHaskell Pointless Haskell] is a library for point-free programming with recursion patterns defined as hylomorphisms. It also allows the visualization of the intermediate data structure of the hylomorphisms with GHood. This feature together with the DrHylo tool allows us to easily visualize recursion trees of Haskell functions.
 
[http://wiki.di.uminho.pt/wiki/bin/view/Alcino/PointlessHaskell Pointless Haskell] is a library for point-free programming with recursion patterns defined as hylomorphisms. It also allows the visualization of the intermediate data structure of the hylomorphisms with GHood. This feature together with the DrHylo tool allows us to easily visualize recursion trees of Haskell functions.

Revision as of 14:42, 22 September 2006

Contents


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 (and to unix shell scripting

): 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 pointful 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 . (==)

1 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 term originated in topology, a branch of mathematics which works with spaces composed of points, and functions between those spaces. So a 'points-free' definition of a function is one which does not explicitly mention the points (values) of the space on which the function acts. In Haskell, our 'space' is some type, and 'points' are values. In the declaration:

 f x = x + 1
we define the function
f
in terms of its action on an arbitrary point
x
. Contrast this with the points-free

version:

 f = (+ 1)

where there is no mention of the value on which the function is acting.

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

3 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 blow 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 [[IRC_channel|#haskell] logs. (Or join #haskell on FreeNode and try it yourself!) 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 . (((.) . (,)) .)

4 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 expression's 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.

5 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:

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:

Squiggol, and the Bird-Meertens Formalism:

Pointless Haskell is a library for point-free programming with recursion patterns defined as hylomorphisms. It also allows the visualization of the intermediate data structure of the hylomorphisms with GHood. This feature together with the DrHylo tool allows us to easily visualize recursion trees of Haskell functions.

This project is written by Manuel Alcino Cunha, see his homepage for more related materials on the topic. An extended verson of his paper Point-free Programming with Hylomorphisms can be found here.

6 Other areas

Combinatory logic and also Recursive function theory can be said in some sense pointfree.

Are there pointfree approaches to relational algebra? See First Steps in Pointfree Functional Dependency Theory written by José Nuno Oliveira. A concise and deep approach. See also the author's homepage and also his many other papers -- many materials related to this topic can be found there.