request clarification of transposition example in McBride/Paterson Applicative paper

Question

Conor McBride's and Ross Paterson's classic paper Applicative programming with effects shows a 'matrice' transposition example:

transpose   :: [[a]] -> [[a]]
transpose [] = repeat []
transpose (xs : xss) = zipWith (:) xs (transpose xss)

transpose is using the "collection point of view" of lists: it pairs functions (here (:)) and inputs elementwise and produce list of resulting outputs.

Therefore, given

v = [[1,2,3],[4,5,6]]

then

transpose  v

results in

[[1,4],[2,5],[3,6]]

Later in the paper they say

If we want to do the same for our transpose example, we shall have to avoid the library’s 'list of successes' (Wadler, 1985) monad and take instead an instance Applicative [] that supports 'vectorization', where pure = repeat and (~) = zapp, yielding

transpose'' :: [[a]] -> [[a]]
transpose''         [] = pure []
transpose'' (xs : xss) = pure (:) <*> xs <*> transpose'' xss

Here, transpose'' is using the "non-deterministic computation point of view" of lists: it applies the function (here (:)) to inputs in turn.

Therefore

 transpose'' v

results in

 [[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]

I feel I am missing some subtle point. I can see that transpose is indeed transposing a "vector" using the collection point of view of lists. But transpose'' (using the non-deterministic computation point of view of lists) seems to have nothing to do with vector transposition.

In other words, transpose and transpose'' seem to be unrelated functions - different examples. Am I missing something?

Answer 1

where pure = repeat and (❄) = zapp, yielding...

This is not the standard list instance. To implement this in Haskell, we need

newtype Zapp a = Zapp { runZapp : [a] } deriving (Functor)
zcons :: a -> Zapp a -> Zapp a
zcons x (Zapp xs) = Zapp $ x : xs

instance Applicative Zapp where
  pure = Zapp . repeat
  Zapp a <*> Zapp b = Zapp $ zapp a b

and then

transpose'' :: Zapp (Zapp a) -> Zapp (Zapp a)
transpose''         (Zapp []) = pure $ Zapp []
transpose'' (Zapp (xs : xss)) = pure zcons <*> xs <*> transpose'' xss

Answer 2

If you make the instance listed for the first example, where the Applicative instance has pure = repeat and <*> = zapp

instance Applicative [] where
    pure = repeat
    (<*>) = zapp

transpose :: [[a]] -> [[a]]
transpose         [] = pure []
transpose (xs : xss) = pure (:) <*> xs <*> transpose xss

main = do
    print . transpose $ [[1,2,3],[4,5,6]]

You get the transposition from transpose:

[[1,4],[2,5],[3,6]]

If, instead, you use the normal Applicative instance for []

instance Applicative [] where
    pure x = [x]
    fs <*> xs = [f x | f <- fs, x <- xs]

transpose :: [[a]] -> [[a]]
transpose         [] = pure []
transpose (xs : xss) = pure (:) <*> xs <*> transpose xss

main = do
    print . transpose $ [[1,2,3],[4,5,6]]

You get

[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]

The boilerplate for both of those examples is:

module Main (
    main
) where

import Prelude hiding (repeat)

infixl 4 <*>
class Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

repeat :: a -> [a]
repeat x = x : repeat x

zapp :: [a -> b] -> [a] -> [b]
zapp (f : fs) (x : xs) = f x : zapp fs xs
zapp _        _        = []