Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Haskell: variable scope in list monad

I was reading an online Haskell book about list monad. In the book, the list monad was defined like this:

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

And then there was an example of list monad usage like this:

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

I'm new to Haskell and my question about the example is, how come the variable 'n' is available inside the lambda expression of return (n,ch). n is defined in the other lambda expression and I don't understand why a variable defined in one lambda expression is available in subsequent lambda expressions. I tried converting the example like 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 got an error saying that the variable n is not available in the scope of the other lambda expression. Maybe the book just presented a simplified version of list monad definition?

like image 873
Jake Avatar asked Jul 28 '17 16:07

Jake


1 Answers

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

is NOT parsed as

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

but as

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

Your translation with concat / map reflects the "wrong" parsing. We can adapt that to the correct one.

The first >>= becomes

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

and now we can translate the inner >>= replacing ??? 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])
like image 75
chi Avatar answered Sep 18 '22 18:09

chi