As an exercise I'm trying to implement interesting parts of the prelude manually. Whenever I spot an opportunity to go point free I take it. However this has led me to a brick wall in the most unlikely place. Using this code:
myelem _ [] = False
myelem x y = if x == head y then True else myelem x (tail y)
I am trying to implement notElem. Here are my attempts:
-- First
mynotelem = not myelem
Understandably blows up due to the types not matching up. This is easily fixed:
-- Second
mynotelem x y = not (myelem x y)
However the explicit declaration of arguments x and y feels ugly and unnecessary, so I try to get it back into point free style.
-- Third
mynotelem = not $ myelem
Which fails with
Couldn't match expected type `Bool'
with actual type `a0 -> [a0] -> Bool'
In the second argument of `($)', namely `myelem'
In the expression: not $ myelem
In an equation for `mynotelem': mynotelem = not $ myelem
Fair enough, the types still don't match up. But how do you fix it? Again you can jump straight to
-- Fourth
mynotelem x y = not $ myelem x y
Which works, but seems dangerously close to just going in circles. I discover it's possible to eliminate one of the arguments:
-- Fifth
mynotelem x = not . (myelem x)
But that pesky x still remains. How do I eliminate it?
We can rewrite your code like this:
mynotelem x = not . (myelem x)
= (not .) (myelem x)
Now recognize that this is just h x = f (g x) with f = (not .) and g = myelem, so we can write it point-free with another use of the (.) operator as h = f . g:
mynotelem = (not .) . myelem
Note how the pattern continues when composing with functions with more arguments:
> let f x y z = x+y+z
> (((sqrt .) .) . f) 1 2 3
2.449489742783178
Alternatively, you can also write it with this funny-looking composition of composition operators:
mynotelem = ((.).(.)) not myelem
For more arguments, the pattern continues like this:
> ((.).(.).(.)) sqrt f 1 2 3
2.449489742783178