13

I am trying to understand how to convert functions to point-free notation in Haskell. I saw this example, but it is more complicated than what I am looking for. I feel like I understand the logic behind it, but when I am trying to execute some simple examples in code I am getting compile errors. I want to try and write this function in point-free style:

f x = 5 + 8/x which I rearranged as f x = (+) 5 $ (/) 8 x

So, I thought it might be something like this:

f = (+) 5 $ (/) 8

but when I run this in ghci I get this message:

No instance for (Num (a0 -> a0))
  arising from the literal `5' at Test.hs:3:9
Possible fix: add an instance declaration for (Num (a0 -> a0))
In the first argument of `(+)', namely `5'
In the first argument of `($)', namely `(+) 5'
In the expression: (+) 5 $ (/) 8
Failed, modules loaded: none.

I don't understand the "No instance for..." message. What do I need to do to write this function in point-free style?

Community
  • 1
  • 1
KJ50
  • 765
  • 1
  • 10
  • 27
  • 4
    I think you may be confused about the [difference between the `$` and `.` operators](http://stackoverflow.com/questions/940382/haskell-difference-between-dot-and-dollar-sign). – hammar Dec 11 '11 at 16:45

4 Answers4

18

$ has a very low precedence. So, f x = (+) 5 $ (/) 8 x actually means f x = (+) 5 $ ((/) 8 x). Instead, rewrite that as

f x = (+) 5 ( (/) 8 x)
f x = ((+) 5) ( ((/) 8) x)
f x = ((+) 5) .  ( ((/) 8) ) x
f = ((+) 5) . ( (/) 8 )
f = (5+) . (8/)

The last expression makes sense: f is the composition of two operations, first divide 8 by what one has, and then add 5 to the result. Remember, g.h means "apply h, then apply g the the result of that".

Prateek
  • 2,377
  • 17
  • 29
13

Conversion from lambda-calculus (which Haskell is a variant of) terms to SKI terms (totally pointfree functions, using only const (K), id (I) and <*> (S)) can be done with the following simple rules:

  1. \x -> x translates to id;
  2. \x -> y without x occurring in y translates to const y;
  3. \x -> f g translates to f' <*> g' where
    • f' is a translation of \x -> f and
    • g' is a translation of \x -> g.

Now you may wonder where does the . come in. There is a special case of the last translation: if f does not have any free occurrences of x, then \x -> f g translates to const f <*> (\x -> g), which is equal to f . (\x -> g).

Using those rules we can convert your function:

f = \x -> ((+) 5) (((/) 8) x) = -- by the special-case (.) rule
((+) 5) . (\x -> (((/) 8) x)) = -- by eta-reduction ((\x -> f x) = f)
((+) 5) . ((/) 8)

Eta-reduction is not necessary to complete the translation, but without it we'd get something messier. For example, the last step would yield ((+) 5) . ((/) 8) . id instead.

Rotsor
  • 13,655
  • 6
  • 43
  • 57
12

The "pointfree" program can be installed with cabal install pointfree, and shows you how to write an expression in pointfree style. For example:

$ pointfree "f x = 5 + 8/x"
f = (5 +) . (8 /)

Explanation of this conversion:

  1. You can use "sections" for infix/operator functions. (a +) == \b -> a + b and (+ a) == \b -> b + a
  2. The . function takes the result of the second parameter, which is a one-argument function, and applies it to the first argument.
dflemstr
  • 25,947
  • 5
  • 70
  • 105
  • I personally force myself to use pointfree style, because: 1. I am forced to make my functions simpler, thus making them more reusable 2. There's a greater chance that I'll actually bother to reuse already written functions, reducing code duplication. – dflemstr Dec 11 '11 at 18:06
  • 1
    Note that (.) is associative but ($) is not, so (.) gives more flexibility in refactoring. And to use (.) you need to master pointfree style. Also monadic combinators such as liftM2, fmap, >>= and >=> almost force you to learn pointfree style. – nponeccop Dec 11 '11 at 20:29
  • 3
    @JFritsch - point free isn't *always* the clearest way to write a function. However, when it is appropriate, it can help you reason about the function, because point free functions are simply compositions of other functions. – Dan Burton Dec 11 '11 at 22:42
  • I installed point free as described, but when I type $ `pointfree` it doesn't know the command. where should I point the PATH to? – wide_eyed_pupil Apr 09 '22 at 03:32
8

You were really close. Allow me to add one more $ to illustrate:

f x = (+) 5 $ (/) 8 $ x

It should be clear that the expression (+) 5 is a function that takes one numeric input and produces a numeric output. The same goes for the expression (/) 8. So you take whatever number is input, x, and first apply the (/) 8 "function", and then apply the (+) 5 "function".

Whenever you have a chain of functions separated by $, you can replace all except the rightmost with . Meaning, if you have a $ b $ c $ d, this is equivalent to a . b . c $ d.

f x = (+) 5 . (/) 8 $ x

At this point, let's actually remove the $ and parenthesize instead.

f x = ((+) 5 . (/) 8) x

Now it should be clear that you can remove the trailing x from both sides:

f = (+) 5 . (/) 8

That is the main idea. If you have f x = expr x, you can "eta reduce" it to f = expr. In order to produce pointfree code, you need simply recognize how the larger function is composed of smaller functions. Partial application is sometimes necessary for point free code (as in this case, (+) 5 and (/) 8 are partially applied). The "pointfree" program is quite helpful for when you don't want to think about it; Lambdabot on the #haskell irc channel uses this program as a plugin, so you don't even have to install it yourself; just ask:

<DanBurton> @pl let f x = 5 + 8 / x in f
<lambdabot> (5 +) . (8 /)
Dan Burton
  • 53,238
  • 27
  • 117
  • 198