Confusion regarding composition in Haskell

Question

I'm working through the Haskell book and I've realized I'm having a hard time understanding function composition. At a very basic level I have a mental model of a pipeline that takes an input and passes it's result to the next function in the composition. For simple functions this is very easy.

Where I'm having difficulty is understanding how the resulting type signatures of composing the functions come to be. For example, if we look at the base definition of elem:

elem :: (Foldable t, Eq a) => a -> t a -> Bool
elem = any . (==)

>:t (==)
(==) :: Eq a => a -> a -> Bool
>:t any
any :: Foldable t => (a -> Bool) -> t a -> Bool

I fail to see how the resulting type signature occurs. If I were given the function and asked to write the type signature I'd be hopelessly lost.

The same goes for the following. In the chapter on Traversable we were told that traverse is just sequenceA and fmap composed:

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse f = sequenceA . fmap f

>:t fmap
fmap :: Functor f => (a -> b) -> f a -> f b
>:t sequenceA
sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)

On their own I understand each functions type signature, but how do they combine to create traverse's type signature?

Super lost here, any help would be greatly appreciated.

Not sure how to explain these particular examples, but generally speaking, I think you should just practice η-expanding/reducing expressions with composition, to get a feel for it. — leftaroundabout
Keep in mind that (a -> Bool) can also be represented by a type variable like b which means you may consider a -> a -> Bool as a -> b and (a -> Bool) -> t a -> Bool as b -> t a -> Bool. Stretching further by naming t a -> Bool as c, (a -> Bool) -> t a -> Bool becomes b -> c. So overall the two turns out to be easily composable. — Redu
sequenceA is not being composed with fmap; it's being composed with fmap f. The distinction is important. — chepner
To get a better sense of how things compose, try expanding out the definition: elem = any . (==) by the definition of (.) is equal to elem = \x -> any ((==) x), which can be “eta-expanded” (adding the missing parameter & argument on both sides) into elem = \x xs -> any ((==) x) xs, whose meaning is more apparent, I hope. With a pinch of syntactic sugar, this is elem x xs = any (x ==) xs. — Jon Purdy

Daniel Wagner Daniel Wagner · Accepted Answer · 2018-12-11T13:49:53

Perhaps merely visually aligning the types will get you part of the way to some intuition about how the pipeline progresses, and help you make progress towards your next point of confusion!

(==)       :: Eq a => a -> (a -> Bool)
any        ::              (a -> Bool) -> (t a -> Bool)
any . (==) :: Eq a => a                -> (t a -> Bool)

To keep the next one on one screen, let's abbreviate Traversable to T and Applicative to A. You also have two fs in your question, one at the computation level and one at the type level. To avoid confusion, I'm going to rename your computation-level f to g instead. So if g :: a -> f b for some Applicative f:

fmap g                   ::  T t       =>               t a -> t (f b)
sequenceA                :: (T t, A f) =>                      t (f b) -> f (t b)
sequenceA . fmap g       :: (T t, A f) =>               t a            -> f (t b)
\g -> sequenceA . fmap g :: (T t, A f) => (a -> f b) -> t a            -> f (t b)

(Wait! How come for fmap g, the constraint on t is Traversable and not Functor? Okay, no problem: we can actually give it the more relaxed type fmap g :: Functor t => .... But since every Traversable must be a Functor, it can also be given this type which makes the parallels more clear.)

Confusion regarding composition in Haskell

2 Answers