CODEWITHSUNDEEP
haskellpointfreecombinators
Raghav Malik
Raghav Malik

Reputation: 840

Haskell point-free style with no functions in the expression

I've been trying to take some simple functions and convert them to point-free style for practice. I started with something like this:

zipSorted x y = (zip . sort) y $ sort x --zipSorted(x, y) = zip(sort(y), sort(x))

and eventually converted it to

zipSorted = flip (zip . sort) . sort

(I'm not sure if this is even the best way to do it but it works)

Now I'm trying to further reduce this expression by not having it depend on zip and sort at all. In other words, I'm looking for this function: (I think its a combinator if my vocabulary isn't mistaken)

P(f, g, x, y) = f(g(y), g(x))

The fact that sort is present twice but only passed in once hinted to me that I should use the applicative functor operator <*> but I can't figure out how for some reason.

From my understanding, (f <*> g)(x) = f(x, g(x)), so I've tried re-writing the first point-free expression in this form:

flip (zip . sort) . sort
(.) (flip $ zip . sort) sort
(flip (.)) sort $ flip (zip . sort)
(flip (.)) sort $ flip $ (zip .) sort

It seems that sort should be x, (flip (.)) should be f, and flip . (zip .) should be g.

p = (flip (.)) <*> (flip . (zip .))
p sort [2, 1, 3] [4, 1, 5]

yields [(1, 1), (4, 2), (5, 3)] as expected, but now I'm lost on how to pull the zip out. I've tried 

p = (flip (.)) <*> (flip . (.))
p zip sort [2, 1, 3] [4, 1, 5]

but this doesn't work. Is there a way to convert that expression to a combinator that factors out zip?

Upvotes: 1

Views: 140

Answers (2)

melpomene
melpomene

Reputation: 85827

Let's start from the beginning:

zipSort x y = zip (sort y) (sort x)

It's slightly weird that it uses its arguments in the opposite order, but we can fix that later with flip.

Here we have a general pattern of a "combining" function of two arguments (here: zip) being passed two values transformed by another function. If we had the same base argument but different transformers, this would have been a liftA2 pattern:

  c (f x) (g x)
==
  liftA2 c f g x

But here it's the opposite: We have the same transform function on both sides (here: sort), but different arguments (x and y). That's on:

  c (f x) (f y)
==
  (c `on` f) x y

In your case we get:

zip (sort y) (sort x)
(zip `on` sort) y x
flip (zip `on` sort) x y

So

zipSort = flip (zip `on` sort)  -- or: flip (on zip sort)

We can further pull out zip and sort by recognizing the standard two-argument-into-one-argument-function composition:

(\x y -> f (g x y)) == (f .) . g

giving

zipSort = ((flip .) . on) zip sort

Note that this function is less general than the pointful version, however. The original function has type

(Ord a, Ord b) => [a] -> [b] -> [(b, a)]

but the pointfree version has type

(Ord a) => [a] -> [a] -> [(a, a)]

because unifying the two sorts forces them to have the same type.

Upvotes: 6

amalloy
amalloy

Reputation: 92057

I just asked lambdabot for the answer, rather than trying to work it out by hand:

<amalloy> @pl \zip sort x y -> (zip . sort) y $ sort x
<lambdabot> join . (((.) . flip) .) . (.)

Upvotes: 2

Related Questions