To me, the most beautiful Haskell code is point-free. As an example of the point-free style, consider the following function which determines the length of a list.
length' :: [a] -> Int length' = sum . map (const 1)
As my knowledge of Haskell has deepened, my appreciation for the ability of the combinators provided by libraries such as
Data.Maybe, to express more complicated functions in the point-free style has grown. (Note that all of these libraries are also important for reasons other than writing point-free code.)
Point-free Haskell makes liberal use of the composition operator,
(.). Recall that the definition of composition is
(.) :: (b -> c) -> (a -> b) -> a -> c (f . g) x = f $ g x = f (g x)
While this operator is immensely useful, it cannot express all forms of composition. For example, consider the problem of determining whether nor not any elements of a list satisfy a predicate (like
Data.List). Written in the pointed style, such a function is simple.
any' :: (a -> Bool) -> [a] -> Bool any' p xs = not $ null $ filter p xs
This function is an excellent candidate to be refactored to be point-free. In fact, whenever the last argument of a function only appears in the last (rightmost) place in its definition, it may be refactored to be point free. For
any', we refactor as
any' p = not . null . filter p
We see again that, by our heuristic, this function should be able to be refactored to be completely point-free by removing the predicate
any' = not . null . filter
Unfortunately, this implementation of
any' will not type-check, giving the following error.
Couldn't match expected type `[a0]' with actual type `[a1] -> [a1]' Expected type: (a1 -> Bool) -> [a0] Actual type: (a1 -> Bool) -> [a1] -> [a1] In the second argument of `(.)', namely `filter' In the second argument of `(.)', namely `null . filter'
There problem is that
filter :: (a -> Bool) -> [a] -> [a] is a function of two arguments, but composition,
(.), expects a function of one argument. It is simple enough to define a function that does the sort of composition we need,
(##) :: (c -> d) -> (a -> b -> c) -> a -> b -> d (f ## g) x y = f $ g x y
Using this function, we may implement
any' in a completely point-free manner as
any' = (not . null) ## filter
This implementation is nice, be we have really just pushed the pointed code into
(##). Before finding a point-free implementation of
(##), let’s rewrite this definition a bit.
(f ## g) x y = f $ g x y = f $ (g x) y = f . (g x) $ y
So we may move one step closer to a point-free implementation with
(f ## g) x = f . (g x) = (f .) (g x) = (f .) $ g x = (f .) . g $ x
(f ## g) = (f .) . g
This implementation is still not quite point-free, so we write
(f ## g) = (f .) . g = (.) (f .) g
(##) f = (.) (f .) = (.) ((.) f) = ((.) . (.)) f
Therefore, the point-free implementation of
(##) = ((.) . (.))
This implementation is a bit mind-bending at first, but really cool once you wrap your head around it.