Point Free problems in Haskell

Question

I am trying to convert the following Haskell code to point free style, to no avail.

bar f g xs = filter f (map g xs )

I'm new to Haskell and any help would be great.

Answer 1

Converting to pointfree style can be done entirely mechanically, though it's hard without being comfortable with the fundamentals of Haskell syntax like left-associative function application and x + y being the same as (+) x y. I will assume you are comfortable with Haskell syntax; if not, I suggest going through the first few chapters of LYAH first.

You need the following combinators, which are in the standard library. I have also given their standard names from combinator calculus.

id :: a -> a                                   -- I
const :: a -> b -> a                           -- K
(.) :: (b -> c) -> (a -> b) -> (a -> c)        -- B
flip :: (a -> b -> c) -> (b -> a -> c)         -- C
(<*>) :: (a -> b -> c) -> (a -> b) -> (a -> c) -- S

Work with one parameter at a time. Move parameters on the left to lambdas on the right, e.g.

f x y = Z

becomes

f = \x -> \y -> Z

I like to do this one argument at a time rather than all at once, it just looks cleaner.

Then eliminate the lambda you just created according to the following rules. I will use lowercase letters for literal variables, uppercase letters to denote more complex expressions.

1. If you have \x -> x, replace with id
2. If you have \x -> A, where A is any expression in which x does not occur, replace with const A
3. If you have \x -> A x, where x does not occur in A, replace with A. This is known as "eta contraction".
4. If you have \x -> A B, then
   1. If x occurs in both A and B, replace with (\x -> A) <*> (\x -> B).
   2. If x occurs in just A, replace with flip (\x -> A) B
   3. If x occurs in just B, replace with A . (\x -> B),
   4. If x does not occur in either A or B, well, there's another rule we should have used already.

And then work inward, eliminating the lambdas that you created. Lets work with this example:

f x y z = foo z (bar x y)
-- Move parameter to lambda:
f x y = \z -> foo z (bar x y)
-- Remember that application is left-associative, so this is the same as
f x y = \z -> (foo z) (bar x y)
-- z appears on the left and not on the right, use flip
f x y = flip (\z -> foo z) (bar x y)
-- Use rule (3) 
f x y = flip foo (bar x y)

-- Next parameter
f x = \y -> flip foo (bar x y)
-- Application is left-associative
f x = \y -> (flip foo) (bar x y)
-- y occurs on the right but not the left, use (.)
f x = flip foo . (\y -> bar x y)
-- Use rule 3
f x = flip foo . bar x

-- Next parameter
f = \x -> flip foo . bar x
-- We need to rewrite this operator into normal application style
f = \x -> (.) (flip foo) (bar x)
-- Application is left-associative
f = \x -> ((.) (flip foo)) (bar x)
-- x appears on the right but not the left, use (.)
f = ((.) (flip foo)) . (\x -> bar x)
-- use rule (3)
f = ((.) (flip foo)) . bar
-- Redundant parentheses
f = (.) (flip foo) . bar

There you go, now try it on yours! There is not really any cleverness involved in deciding which rule to use: use any rule that applies and you will make progress.

Answer 2

Both of the existing answers don't really answer your specific question in a way that's elucidating: one is "here are the rules, work it out for yourself" and the other is "here is the answer, no information about how the rules generate it."

The first three steps are really easy and consist in removing a common x from something of the form h x = f (g x) by writing h = f . g. Essentially it's saying "if you can write the thing in the form a $ b $ c $ ... $ y $ z and you want to remove the z, change all the dollars to dots, a . b . c . ... . y:

bar f g xs = filter f (map g xs)
           = filter f $ (map g xs)
           = filter f $ map g $ xs -- because a $ b $ c == a $ (b $ c).
bar f g    = filter f . map g
           = (filter f .) (map g)
           = (filter f .) $ map $ g
bar f      = (filter f .) . map

So this last f is the only tricky part, and it's tricky because the f is not at the "end" of the expression. But looking at it, we see that this is a function section (. map) applied to the rest of the expression:

bar f = (.) (filter f) . map
bar f = (. map) $ (.) $ filter $ f
bar   = (. map) . (.) . filter

and that's how you reduce an expression when you don't have complicated things like f x x and the like appearing in it. In general there is a function flip f x y = f y x which "flips arguments"; you can always use that to move the f to the other side. Here we have flip (.) map . (.) . filter if you include the explicit flip call.

Answer 3

I asked lambdabot, a robot who hangs out on various Haskell IRC channels, to automatically work out the point-free equivalent. The command is @pl (pointless).

10:41 <frase> @pl bar f g xs = filter f (map g xs )
10:41 <lambdabot> bar = (. map) . (.) . filter

The point free version of bar is:

bar = (. map) . (.) . filter

This is arguably less comprehensible than the original (non-point-free) code. Use your good judgement when deciding whether to use point-free style on a case-by-case basis.

Finally, if you don't care for IRC there are web-based point-free converters such as pointfree.io, the pointfree command line program, and other tools.