Austin Rochford {Math, Data, Software}

Generalized Composition in Haskell

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 Control.Arrow, Control.Monad, Control.Applicative, Data.Either, and 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 any from 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 p.

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

Therefore

(f ## g) = (f .) . g

This implementation is still not quite point-free, so we write

(f ## g) = (f .) . g
         = (.) (f .) g

so

(##) f = (.) (f .)
       = (.) ((.) f)
       = ((.) . (.)) f

Therefore, the point-free implementation of (##) is

(##) = ((.) . (.))

This implementation is a bit mind-bending at first, but really cool once you wrap your head around it.