# 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
= sum . map (const 1) length'
```

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
. g) x = f $ g x
(f = 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
= not $ null $ filter p xs any' 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

`= not . null . filter p any' 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`

.

`= not . null . filter any' `

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
## g) x y = f $ g x y (f
```

Using this function, we may implement `any'`

in a completely point-free manner as

`= (not . null) ## filter any' `

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.

```
## g) x y = f $ g x y
(f = f $ (g x) y
= f . (g x) $ y
```

So we may move one step closer to a point-free implementation with

```
## g) x = f . (g x)
(f = (f .) (g x)
= (f .) $ g x
= (f .) . g $ x
```

Therefore

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

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

```
## g) = (f .) . g
(f = (.) (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.