CODEWITHSUNDEEP
haskell
Shane Unger
Shane Unger

Reputation: 378

Confusion regarding composition in Haskell

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.

Upvotes: 5

Views: 203

Answers (2)

Daniel Wagner
Daniel Wagner

Reputation: 153352

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.)

Upvotes: 8

duplode
duplode

Reputation: 34398

All Haskell functions take just one argument -- even the ones we often think of as taking multiple arguments. Consider your elem example:

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

The type of (==) can be read as (==) :: Eq a => a -> (a -> Bool): it takes an a value (a can be anything which is an instance of Eq) and gives an a -> Bool function. any, in turn, takes an a -> Bool function (a can be anything) and gives a t a -> Bool function (t can be anything which is an instance of Foldable). That being so, the intermediate type in the any . (==) pipeline is Eq a => a -> Bool.

Upvotes: 3

Related Questions