CODEWITHSUNDEEP
haskellfunctional-programmingzipapplicative
DennisVDB
DennisVDB

Reputation: 1357

Partially applying <*> with zip

I started to look at some Haskell code and found:

foo :: ([a] -> [b]) -> [a] -> [(a, b)]
let foo = (<*>) zip

I don't understand how this works, ap expects a f (a -> b) -> f a but zip is of type [a] -> [b] -> ([a, b]). I understand that f a -> f b would match [a] -> [b], but not f (a -> b).

Upvotes: 3

Views: 95

Answers (1)

amalloy
amalloy

Reputation: 91857

Let's work out the types by hand. First, what are the types of the relevant expressions?

(<*>) :: Applicative f => f (a -> b) -> f a -> f b
zip :: [a] -> [b] -> [(a, b)]

Now, we need to unify the type of zip with the type of the first argument to (<*>). Let's rename the unrelated as and bs:

Applicative f => f (a -> b)
                 [c] -> [d] -> [(c, d)]

First, what is f? What Applicative are we working in? The type of the bottom half is a function, so f must be ((->) [c]), or "functions taking a list of c as input". And once we've done that, we can see that:

f ~ ((->) [c])
a ~ [d]
b ~ [(c, d)]

Now that we've got the types to match up, we can look up the definition of (<*>) for functions:

instance Applicative ((->) a) where
    pure = const
    (<*>) f g x = f x (g x)

Substituting zip for f here, and rewriting as a lambda, yields:

(<*>) zip = \g x -> zip x (g x)

So, this needs a function from [a] -> [b] and an [a], and zips the input list with the result of calling the function on it.

That makes sense mechanically, but why? What more general understanding can lead us to this conclusion without having to work everything out by hand? I'm not sure my own explanation of this will be useful, so you may want to study the instances for ((->) t) yourself if you don't understand what's going on. But in case it is useful, here is a handwavy expanation.

The Functor, Applicative, and Monad instances for ((->) t) are the same as Reader t: "functions which have implicit access to a value of type t". (<*>) is about calling a function inside of an Applicative wrapper, which for functions is a two-argument function. It arranges that the "implicit" argument be passed to f, yielding another function, and calls that function with the value obtained by passing the implicit argument to g as well. So, (<*>) f, for some f, is "Give me another function, and a value x, and I'll pass x to both f and the other function".

Upvotes: 7

Related Questions