[Haskell-beginners] Pointfree style

[Brent Yorgey]

On Tue, Nov 11, 2008 at 12:40:19PM +0100, Bas van Gijzel wrote:
> Hi,
> 
> I'm trying to understand pointfree style better, but it's not coming along
> as well as I'd like it to.
> The thing I can't get to work is to reduce an argument that is used more
> than once in a function.
> 
> My function looks like this now (which works like it should):
> f x = g ((h . i) x) x
> 
> But I'd like to reduce the last argument x. I've looked at the wiki[1] but I
> couldn't find a systematic way to obtain pointfree functions when they get
> more complicated.
> Any pointers to pages or papers with more examples of obtaining pointfree
> functions are appreciated.

If you're doing this just to learn, great.  If you're doing this
because you think a pointfree style is somehow 'better', you should
know that there are limits.  =) In the case of your function f above
(and, in general, with any function that uses its argument more than
once) I would leave it as it is.  The really important things to know
are composition, i.e.

  f x = g (h (x))    becomes  f x = (g . h) x

and eta-reduction, i.e.

  f x = foo x   becomes  f = foo.

There are other things that can be nice, such as flip, and various
Arrow combinators (such as (&&&), (***)) for the (->) instance of
Arrow [1] for use with functions involving tuples.  Going much beyond that
is often just obfuscation, IMO.

But to answer your question, a systematic way to transform functions
which use their argument more than once into pointfree versions is to
use the ((->) e) (aka reader) monad [2]:

  f x = g (h x) x   becomes   f x = (h >>= g) x

Essentially, in the ((->) e) monad, (>>=) is a combinator to do
exactly what you are asking about -- compose two functions with a
duplicated input.  Of course, if you dig into the implementation of
(>>=) for the ((->) e) monad, you will eventually find a function
which is not point-free -- this is unavoidable at some level; you
can't actually duplicate an arbitrary thing without giving it a name.

Applying this to your example:

  f x = g ((h . i) x) x
  f x = ((h . i) >>= g) x
  f   = (h . i) >>= g

-Brent

[1] http://haskell.org/ghc/docs/latest/html/libraries/base/Control-Arrow.html
[2] http://haskell.org/ghc/docs/latest/html/libraries/base/Control-Monad-Instances.html