How does the bind operator get invoked multiple times

user_3276646 0
Viewed 64

First I would like to apologize if I am not asking the correct question. I realize that there are some fundamental concepts that I don't quite understand about Monads and the bind operator which is making it difficult to formulate my question. I am having a hard time wrapping my head around how the following code is creating a list of tuples.

ordPairs :: Ord a => [a] -> [(a, a)]
ordPairs xs =
   xs >>= \x1 ->
   xs >>= \x2 ->
   if x1 < x2 then [(x1, x2)] else []

main = print $ ordPairs [1, 2, 4, 6, 7, 8, 3, 4, 5, 6, 2, 9, 7, 8, 45, 4]

I understand the type declaration states that it returns a list of tuples [(a, a)]. What I can't figure out is how is this code "looping" through each item in the list? Looking at this as a beginner it looks as if it only passes the first and second item forward x1 and x2 and then ends with the if then else expression. Is this code being desugared into multiple iterations and building the list under the hood? I guess what I am asking is how is this code iterating through each item in the list and building a list of tuples at the end?

haskell
1 Answers

It might help to understand "where the parentheses are". The right-hand side of the ordPairs definitions is parsed like this:

xs >>= (\x1 -> xs >>= (\x2 -> if x1 < x2 then [(x1, x2)] else []))

As you can see here, the if-then-else expression does not stand alone, it's actually the body of an anonymous function:

\x2 -> if x1 < x2 then [(x1, x2)] else []

which can, obviously, be invoked multiple times for different values of x2. What invokes it? Well, the second >>= operator, of course. The "outer" loop works similarly, with the first >>= operator invoking another anonymous function multiple times:

\x1 -> xs >>= (\x2 -> ...)

For this example, you could replace the >>= operator with your own custom bind function. Note that it's just a plain function. There's no special desugaring or secret iterating going on. The function itself does the iterating using recursion:

bind :: [a] -> (a -> [b]) -> [b]
bind (x:xs) f = f x ++ bind xs f
bind [] _ = []

You could also write bind like this, if you prefer:

bind xs f = concatMap f xs
-- or even `bind = flip concatMap`, as per @WillemVanOnsem's comment

Or as a list comprehension.

bind xs f = [y | x <- xs, y <- f x]

This last one is the actual definition of the >>= operator for the list monad. See GHC/Base.hs.

With any of these definitions, the following will work just like your original:

bind :: [a] -> (a -> [b]) -> [b]
bind (x:xs) f = f x ++ bind xs f
bind [] _ = []

ordPairs :: Ord a => [a] -> [(a, a)]
ordPairs xs =
   xs `bind` \x1 ->
   xs `bind` \x2 ->
   if x1 < x2 then [(x1, x2)] else []

main = print $ ordPairs [1,2,4,6,7,8,4,5,6,2,9,7,8,45,4]
user_72030160
Related