Why does zipWith.zipWith work?

Question

I am implementing a function combine :: [[a]] -> [[b]] -> (a -> b -> c) -> [[c]] which given two 2D lists, applies a given function f :: a -> b -> c to the entries of the 2D list. In other words:

          [[a, b, c],    [[r, s, t],          [[f a r, f b s, f c t], 
combine    [d, e, g],     [u, v, w],   f   =   [f d u, f e v, f g w],
           [h, i, j]]     [x, y, z]]           [f h x, f i y, f j z]]

Now I suspect that combine = zipWith . zipWith, because I have tried it out and it is giving me the intended results, e.g.

(zipWith . zipWith) (\x y -> x+y) [[1,2,3],[4,5,6]] [[7,8,9],[10,11,12]]

gives the expected result [[8,10,12],[14,16,18]], but I cannot understand why this works, because I don't understand how the type of zipWith . zipWith turns out to be (a -> b -> c) -> [[a]] -> [[b]] -> [[c]].

Is (.) here still carrying out the usual function composition? If so, can you explain how this applies to zipWith?

Answer 1

To infer the type of an expression such as zipWith . zipWith, you can simulate the unification in your head the following way.

The first zipWith has type (a -> b -> c) -> ([a] -> [b] -> [c]), the second (s -> t -> u) -> ([s] -> [t] -> [u]) and (.) has type (m -> n) -> (o -> m) -> (o -> n).

For it to typecheck, you need:

• m = (a -> b -> c)
• n = ([a] -> [b] -> [c])
• o = (s -> t -> u)
• m = ([s] -> [t] -> [u]) => a = [s], b = [t], c = [u] because of the first constraint

Then the returned type is o -> n which is (s -> t -> u) -> ([a] -> [b] -> [c]) from the constraints and going one step further (s -> t -> u) -> ([[s]] -> [[t]] -> [[u]]).

Answer 2

Yes, . is the normal function composition operator:

Prelude> :type (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

One way to look at it is that it takes an a value, first calls the a -> b function, and then uses the return value of that function to call the b -> c function. The result is a c value.

Another way to look at (zipWith . zipWith), then, is to perform an eta expansion:

Prelude> :type (zipWith . zipWith)
(zipWith . zipWith) :: (a -> b -> c) -> [[a]] -> [[b]] -> [[c]]

Prelude> :t (\x -> zipWith $ zipWith x)
(\x -> zipWith $ zipWith x)
  :: (a -> b -> c) -> [[a]] -> [[b]] -> [[c]]

Prelude> :t (\x -> zipWith (zipWith x))
(\x -> zipWith (zipWith x))
  :: (a -> b -> c) -> [[a]] -> [[b]] -> [[c]]

The type of zipWith itself:

Prelude> :type zipWith
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

So, in the above lambda expression, x must be (a -> b -> c), and hence zipWith x must have the type [a] -> [b] -> [c].

The outer zipWith also needs a function (a1 -> b1 -> c1), which matches zipWith x if a1 is [a], b1 is [b], and c1 is [c].

So, by replacement, zipWith (zipWith x) must have the type [[a]] -> [[b]] -> [[c]], and therefore the type of the lambda expression is (a -> b -> c) -> [[a]] -> [[b]] -> [[c]].

Answer 3

Another way of seeing it is that lists with the zipping operation form an Applicative, and the composition (nesting) of Applicatives is still Applicative:

λ import Control.Applicative
λ import Data.Functor.Compose
λ let l1 = ZipList [ZipList [1,2,3], ZipList [4,5,6]]
λ let l2 = ZipList [ZipList [7,8,9], ZipList [10,11,12]]
λ getCompose $ (+) <$> Compose l1 <*> Compose l2
ZipList {getZipList = [ZipList {getZipList = [8,10,12]},
                       ZipList {getZipList = [14,16,18]}]}

The ZipList newtype is required because "bare" lists have a different Applicative instance, which forms all combinations instead of zipping.