Haskell: variable scope in monad list

Question

I read the Haskell online book on list monad. In the book, the list monad was defined as follows:

instance Monad [] where return x = [x] xs >>= f = concat (map f xs) fail _ = [] 

And then there was an example of using a list monad as follows:

 Prelude> [1,2] >>= \n -> ['a','b'] >>= \ch -> return (n,ch) [(1,'a'),(1,'b'),(2,'a'),(2,'b')] 

I am new to Haskell, and my question is about an example: where did the variable "n" come from in the lambda expression return (n,ch) . n defined in another lambda expression, and I don’t understand why the variable defined in one lambda expression is available in subsequent lambda expressions. I tried to convert the example as shown below according to the list monad definition:

 Prelude> concat (map (\ch -> return (n, ch)) (concat (map (\n -> ['a', 'b']) [1, 2]))) <interactive>:32:29: error: Variable not in scope: n 

But, as you can see, I received an error message indicating that the variable n not available in the scope of another lambda expression. Maybe the book just introduced a simplified version of the definition of a list monad?

Answer 1

 [1,2] >>= \n -> ['a','b'] >>= \ch -> return (n,ch) 

NOT handled as

 [1,2] >>= (\n -> ['a','b']) >>= (\ch -> return (n,ch)) 

but how

 [1,2] >>= \n -> (['a','b'] >>= (\ch -> return (n,ch))) 

Your translation with concat / map reflects "incorrect" parsing. We can adapt it to the right one.

First >>= becomes

 concat (map (\n -> ???) [1,2]) 

and now we can translate the internal >>= replacement ??? as needed:

 ??? = concat (map (\ch -> ???2) ['a','b']) ???2= return (n,ch) 

Result:

 concat (map (\n -> concat (map (\ch -> return (n,ch)) ['a','b'])) [1,2]) 

Answer 2

Because your expression:

 [1,2] >>= \n -> ['a','b'] >>= \ch -> return (n,ch) 

is equivalent to:

 -- body of the lambda expression -- _________^_______________________ -- / \ [1,2] >>= (\n -> (['a','b'] >>= \ch -> return (n,ch))) -- \________________ _________________________/ -- v -- entire right operand 

So, to the right of the first >>= you wrote a lambda expression .

Monad Definition [] :

 instance Monad [] where return x = [x] xs >>= f = concat (map f xs) 

So you wrote:

 [1,2] >>= (\n -> (['a','b'] >>= \ch -> return (n,ch))) -> concat (map (\n -> (['a','b'] >>= \ch -> return (n,ch)) [1,2]) -> concat (map (\n -> concat (map (\ch -> return (n,ch)) ['a','b'])) [1,2]) -> concat (map (\n -> concat (map (\ch -> [(n,ch)]) ['a','b'])) [1,2]) 

So n is in the scope of the expression \ch -> [(n,ch)] . And with the last statement we get:

 Prelude> concat (map (\n -> concat (map (\ch -> [(n,ch)]) ['a','b'])) [1,2]) [(1,'a'),(1,'b'),(2,'a'),(2,'b')] 

Answer 3

Well, the answers @chi and @Willem Van Onsem are great for variety use only. I would like to mention that understanding lists is just syntactic sugar for this monadic work:

 Prelude> [(x,y) | x <- [1,2], y <- ['a', 'b']] [(1,'a'),(1,'b'),(2,'a'),(2,'b')] 

However, since lists are also instances of the application functor class in Haskell, another good way to do this without touching the monad instance would be:

 Prelude> (,) <$> [1,2] <*> ['a','b'] [(1,'a'),(1,'b'),(2,'a'),(2,'b')] 

I would like to clarify the latter a little,

(,) is actually a function that takes two arguments and with a type signature; a -> b -> (a,b) . Whereas <$> is an inline form of fmap . Therefore, applying (,) <$> [1,2] , we obtain an applicative functor (list of functions), such as [(,) 1, (,) 2] . Now we can apply the applicative operator <*> , which has a signature of type Applicative f => f (a -> b) -> fa -> fb In a signature of type f it should not be confused with a function. It denotes a functor, which is the type of [] (list) here. Which says that <*> parses the contained functions (functions) from the functor and applies them to the provided functor containing the value (s) to return the result of these applications to the same type of functor. Therefore, it is obvious that since list applications are defined by all elements one to one, the result is a list of tuples of all combinations.