2

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.

2 Answers 2

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])
3
  • 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, 2014 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, 2014 at 3:22
  • Actually we can only have one functor instance and ZipLists are meant to work over infinite lists. I think the OP just wants zip :) Feb 14, 2014 at 5:48
1

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].

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.