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

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.

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])
``````
• Very interesting. It seems to sink in now. I find explaining all of it in tutorials applied to just lists could have been much more intuitive to read, but I understand there are many more types of monads, and keeping it generic allows for much broader way of thinking. – Alex Pakka Feb 14 '14 at 3:15
• One of the reasons I liked learn you a haskell was that it gives so many examples of implementing different classes. He usually shows Maybe, Either, List and IO. I also just edited the code so you can see that you don't need to limit yourself to naming that function cartesianProd because it also acts like dotProduct or even functions I don't have names for if you use it for other types. – WuHoUnited Feb 14 '14 at 3:22
• Actually we can only have one functor instance and `ZipList`s are meant to work over infinite lists. I think the OP just wants `zip` :) – Daniel Gratzer Feb 14 '14 at 5:48

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 `a`s and `b`s 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]`.