do notation and bind signature

Question

I'm new to Haskell and functional programming and I was wondering why an example like this (the "nested loop") works:

do
  a <- [1, 2, 3]
  b <- [4, 5, 6]
  return $ a * 10 + b

Some of the stuff below is kind of pseudo-Haskell syntax, but I hope it illustrates my understanding.

It's my understanding that it's turned into something like this

[1, 2, 3] >>= \a -> 
          ([4, 5, 6] >>= \b -> 
                     return $ b * 10 + a)

I think this expression

[4, 5, 6] >>= \b -> return $ b * 10 + a

Produces a list of partially applied functions

[[40 + a], [50 + a], [60 + a]]

Concatenated to

[40 + a, 50 + a, 60 + a]

For the last step, something looks like this

[1, 2, 3] >>= \a -> [40 + a, 50 + a, 60 + a]

Becomes

[41, 51, 61, 42, 52, ... ]

My dilemma is because the type of return $ b * 10 + a seems to be different from the type of [40 + a, 50 + a, 60 + a].

Shouldn't the bind signature be like this?

 (>>=)  :: m a -> (a -> m b) -> m b

In this example seems to be like

[int] -> (int -> [int -> int -> int]) -> [int -> int]

And

[int] -> (int -> [int -> int]) -> [int]

Answer 1

I think the reason it's confusing is because you're working on this inside-out, by trying to think of the inner bind as producing a list of partially applied functions. It doesn't: a and b are closed over, not arguments waiting to be applied. Instead, start from the outside of the expression and work inwards:

[1, 2, 3] >>= \a -> (...)

For each item in the list, produce a list somehow, with access to a as a name for an item in the original list

... [4, 5, 6] >>= \b -> (...)

To produce the list needed by the previous step, produce a new list with access to both a and b, one from each of the two numbered lists.

... return $ b * 10 + a

To produce the list needed by the previous step, create a list of a single item, whose value is b * 10 + a.

You ask why the type of return $ b * 10 + a is different from the type of [40 + a, 50 + a, 60 + a], but they're not: both are of type [Int]. Neither involves any functions. Rather, they both are lists of numbers, constructed by referring to already-closed-over variables. And indeed (>>=) has exactly the type that it should: it takes a list of int, and a function for producing a list of int from a single int, and gives back a different list of int:

(>>=) :: [Int] -> (Int -> [Int]) -> [Int]