Reputation: 378
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
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 f
s 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
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