Why lifting of binary function into the list monads goes over all the element combinations?

Question

Say, if I want to create a cartesian product of two lists, I could do (here in Haskell, but I can do the same e.g. in Scala or any other FP-able language)

cartesianProd = liftM2 (,)

then

>cartesianProd [1,2] [3,4]
>[(1,3),(1,4),(2,3),(2,4)] 

Obviously, using (lifting) + instead of tuple pairing, will produce list of sums of all combinations.

By FP definition, "lifting is a concept which allows you to transform a function into a corresponding function within another (usually more general) setting." The way I understand it, if I have monadic arguments, I can transform my binary function to work with them via liftM2. Where does the cartesian product comes from, though? Intuitively, I would expect [(1,3), (2,4)] from the example above.

Answer 1

I don't know much about Haskell but for your question I would recommend reading this section of Learn You a Haskell: http://learnyouahaskell.com/functors-applicative-functors-and-monoids#the-newtype-keyword .

The gist of it is that some types could satisfy classes such as functor or monad laws in more than one way. Lists for instance could be applicative functors in the way that they are in the haskell standard library (applies the function to every possibility from each list), or they could be applicative functors in the way that you expect them to (apply the function to corresponding elements in the lists).

The designers of haskell thought that the cartesian product version was more useful so they made that the default interpretation. They also however realized that your interpretation also satisfied appropriate laws and was also useful and so you should try running the below code.

module Main where

import qualified Control.Applicative as CA

prod :: (CA.Applicative f) => f a -> f b -> f (a, b)
prod = CA.liftA2 (,)

main :: IO ()
main = do 
        print $ prod [1,2] [3,4]
        print . CA.getZipList $ prod (CA.ZipList [1,2]) (CA.ZipList [3,4])

Answer 2

Well the reason is that the M in liftM2 means monad. In fact liftM2 is defined as

 liftM2 :: Monad m => (a -> b -> c) -> m a -> m b -> m c
 liftM2 f a b = do
   a' <- a
   b' <- b
   return (f a b)

This relies on monadic bind operation >>= :: m a -> (a -> m b) -> m b. In a list, >>= is equivalent to concatMap, so your code is

 cartProd f a b = concatMap (\a' -> concatMap (\b' -> f a b) b) a

This applies (,) to each and every pair of as and bs in our list and so we get a cartesian product. Incidentally it would be better practice to use liftA2 which works over all monads + applicatives.

I'll skip over the thorny issue of why the list monad is concatMap and relegate that till you come across it in a nice book like LYAH or Real World Haskell. Instead the behavior you want is zip or the more general zipWith :: (a -> b -> c) -> [a] -> [b] -> [c].