2
$\begingroup$

In Tacit Programming page on wikipedia, it is stated that the point free version of

p x y z = f (g x y) z is
p = ((.) f) . g

and that the point free version of

mf criteria operator list = filter criteria (map operator list) is
mf = (. map) . (.) . filter.

I can not figure out how can we get from one side to the other, in either way. Would you please show me a step by step explanation of why those equivalences hold?

$\endgroup$
4
$\begingroup$

Going from the point-free version to the lambda version is mechanical. Remember that composition is defined by (f . g) = (.) f g = \x. f (g x), so (f . g) x = f (g x). Remember also that (f . g) is syntactic sugar for (.) f g and f x y is shorthand for (f x) y. It's easier to follow what's going on if you apply one argument at a time.

p = ((.) f) . g
p x = (((.) f) . g) x = ((.) f) (g x) = (.) f (g x)
p x y = (p x) y = ((.) f (g x)) y = (.) f (g x) y = (f . g x) y = f (g x y)
p x y z = (p x y) z = (f (g x y)) z = f (g x y) z

To go in the other direction, arrange the function calls so that there is a single occurrence of the function's parameter in the function body, and arrange it to be at the end of the call. In addition to . for composition, this may require the use of auxiliary functions such as flip to change the order of arguments.

p x y z = f (g x y) z
p x y = f (g x y)
p x = \y. f (g x y) = \y. f ((g x) y) = \y. (f . g x) y = (f . g x) = ((.) f) (g x)
p = \x. ((.) f) (g x) = \x. ((.) f . g) x = ((.) f . g)
$\endgroup$
  • $\begingroup$ Thank you very much for your clear answer. I also found the answer to the second equality (filter criteria (map operator list)) that I have posted as a separate answer. Can you please add it to yours just to make yours complete? $\endgroup$ – al pal Sep 25 '19 at 21:10
  • $\begingroup$ Can you please give me an example of the case where you would arrange the function call so that there is a single occurrence of the function's parameter? $\endgroup$ – al pal Sep 25 '19 at 21:16
0
$\begingroup$

I found the following at [Haskell-cafe] Exercise in point free-style which states that:

func2 f g l = filter f (map g l)
func2 f g = (filter f) . (map g)    -- definition of (.)
func2 f g = ((.) (filter f)) (map g)    -- desugaring
func2 f = ((.) (filter f)) . map    -- definition of (.)
func2 f = flip (.) map ((.) (filter f)) -- desugaring, def. of flip
func2 = flip (.) map . (.) . filter     -- def. of (.), twice
func2 = (. map) . (.) . filter      -- add back some sugar
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.