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]
Here’s how it desugars and works operationally. You’re right that this:
do
a <- [1, 2, 3]
b <- [4, 5, 6]
return $ a * 10 + b
Desugars to this:
[1, 2, 3] >>= \a ->
[4, 5, 6] >>= \b ->
return $ b * 10 + a
Which in turn is using the list instance of Monad, whose definitions of >>= and return (or pure) we can inline:
concatMap
(\a -> concatMap
(\b -> [b * 10 + a])
[4, 5, 6])
[1, 2, 3]
We can break apart concatMap into concat and map:
concat
(map
(\a -> concat
(map
(\b -> [b * 10 + a])
[4, 5, 6]))
[1, 2, 3])
Now we can reduce this, and here I think is where you were encountering difficulty: reduction happens from the outside in, and doesn’t produce partially applied functions in this case; rather, it captures a in the closure of the inner lambda (\b -> …). First, we map (\a -> …) over [1, 2, 3]:
concat
[ (\a -> concat
(map
(\b -> [b * 10 + a])
[4, 5, 6])) 1
, (\a -> concat
(map
(\b -> [b * 10 + a])
[4, 5, 6])) 2
, (\a -> concat
(map
(\b -> [b * 10 + a])
[4, 5, 6])) 3
]
==
concat
[ let a = 1
in concat
(map
(\b -> [b * 10 + a])
[4, 5, 6])
, let a = 2
in concat
(map
(\b -> [b * 10 + a])
[4, 5, 6])
, let a = 3
in concat
(map
(\b -> [b * 10 + a])
[4, 5, 6])
]
Then we can reduce the inner maps:
concat
[ let a = 1
in concat
[ (\b -> [b * 10 + a]) 4
, (\b -> [b * 10 + a]) 5
, (\b -> [b * 10 + a]) 6
]
, let a = 2
in concat
[ (\b -> [b * 10 + a]) 4
, (\b -> [b * 10 + a]) 5
, (\b -> [b * 10 + a]) 6
]
, let a = 3
in concat
[ (\b -> [b * 10 + a]) 4
, (\b -> [b * 10 + a]) 5
, (\b -> [b * 10 + a]) 6
]
]
==
concat
[ let a = 1
in concat
[ let b = 4 in [b * 10 + a]
, let b = 5 in [b * 10 + a]
, let b = 6 in [b * 10 + a]
]
, let a = 2
in concat
[ let b = 4 in [b * 10 + a]
, let b = 5 in [b * 10 + a]
, let b = 6 in [b * 10 + a]
]
, let a = 3
in concat
[ let b = 4 in [b * 10 + a]
, let b = 5 in [b * 10 + a]
, let b = 6 in [b * 10 + a]
]
]
Which we can then simplify by replacing variables with their values:
concat
[ concat
[ [4 * 10 + 1]
, [5 * 10 + 1]
, [6 * 10 + 1]
]
, concat
[ [4 * 10 + 2]
, [5 * 10 + 2]
, [6 * 10 + 2]
]
, concat
[ [4 * 10 + 3]
, [5 * 10 + 3]
, [6 * 10 + 3]
]
]
And reducing the calls to concat:
concat
[ [ 4 * 10 + 1
, 5 * 10 + 1
, 6 * 10 + 1
]
, [ 4 * 10 + 2
, 5 * 10 + 2
, 6 * 10 + 2
]
, [ 4 * 10 + 3
, 5 * 10 + 3
, 6 * 10 + 3
]
]
==
[ 4 * 10 + 1
, 5 * 10 + 1
, 6 * 10 + 1
, 4 * 10 + 2
, 5 * 10 + 2
, 6 * 10 + 2
, 4 * 10 + 3
, 5 * 10 + 3
, 6 * 10 + 3
]
And of course the individual expressions:
[ 41, 51, 61
, 42, 52, 62
, 43, 53, 63
]
A case where you will see a list of partially applied functions is when using the Applicative instance of lists, for example, the equivalent to your code:
(\a b -> b * 10 + a) <$> [1, 2, 3] <*> [4, 5, 6]
The definition of <$>/fmap for lists is just map, so we partially apply the first argument of the lambda, producing a list of type [Int -> Int], then (<*>) :: (Applicative f) => f (a -> b) -> f a -> f b, here at type [Int -> Int] -> [Int] -> [Int], applies each function in its left operand to each value in its right operand.