5

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.

Shane Unger
  • 378
  • 1
  • 7
  • 1
    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 Dec 11 '18 at 13:42
  • 1
    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 Dec 11 '18 at 14:20
  • 2
    `sequenceA` is *not* being composed with `fmap`; it's being composed with `fmap f`. The distinction is important. – chepner Dec 11 '18 at 15:49
  • 1
    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 Dec 12 '18 at 01:16

2 Answers2

8

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

Daniel Wagner
  • 145,880
  • 9
  • 220
  • 380
  • : `Applicative f :: a -> f b` ? that's a strange `f` there. what is it? > could we lessen the cognitive load perhaps, and use `g` for one of them perhaps? – Will Ness Dec 11 '18 at 14:14
  • @WillNess Okay. You convinced me. =) – Daniel Wagner Dec 11 '18 at 14:18
  • I'm here to serve. :) BTW kudos for aligning the types. Been doing this for years, myself.... – Will Ness Dec 11 '18 at 14:18
  • 1
    one last thing: it might be worth it adding `g :: A f => a -> f b` line above the `fmap :: ... t a -> t (f b)` line, for even more visually aligned stuff. For your consideration. – Will Ness Dec 11 '18 at 14:24
  • 1
    @WillNess The role of `g` in type inference is a bit backwards compared to the other terms, because it is going to be lambda-abstracted later. I tried to finesse this a bit in my answer (e.g. I wrote the somewhat awkward "`g :: a -> f b` for some `Applicative f`" rather than "`g :: Applicative f => a -> f b`"). Writing `g :: A f => a -> f b` in the sequence of type signatures would definitely be imprecise in that sense; so unlike your previous suggestion this one is not merely about the presentation but about the correctness. And I'm not going to put `g :: exists f a b. A f *> a -> f b`... – Daniel Wagner Dec 11 '18 at 14:53
  • hmm. good thing I didn't do that edit then. I also thought `fmap g` should've had both constraints on it, too. I really need to read up on the finer points of Haskell's types, been putting it off for far too long. Where can I see what that `*>` thing means? Do you know of one definitive source on Haskell's type system / inference, or should I start at Wikipedia's Hindley-Milner page and go through the books / papers, for that? – Will Ness Dec 11 '18 at 16:44
  • @WillNess `*>` is syntax invented by ski on the #haskell IRC channel, definitely not widely or standardly known. It's dual to `=>`; where you should think of `c => t` as being a function that takes evidence of constraint `c` and results in a computation of type `t`, you should think of `c *> t` as being a pair of evidence for constraint `c` and a computation of type `t`. For H-M, there is some discussion and resource links [here](https://stackoverflow.com/q/12532552/791604) you might like. – Daniel Wagner Dec 11 '18 at 18:39
3

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.

duplode
  • 33,731
  • 7
  • 79
  • 150