Search code examples
haskelllist-comprehensiondo-notation

What does "<-" mean?

In this tutorial http://learnyouahaskell.com/starting-out the author writes this piece of code.

boomBangs xs = [ if x < 10 then "BOOM!" else "BANG!" | x <- xs, odd x]

And then later executes it like this

boomBangs[7..13]

And my question is, what does the "<-" operator do? To me this seems like it would cause recursive behavior, since I am referencing what looks to me like a function inside a function, or perhaps defining how to create a list comprehension.

Searching around I found this explanation by chi on a different question:
"x <- action runs the IO action, gets its result, and binds it to x"

Is the "<-" in the question linked above different to the "<-" used in the code I copied above? Does xs run inside xs? I'd be grateful if someone could explain to me what's going on here.

Solution

  • Your list comprehension is in essence just syntactical sugar for:

    import Control.Monad(guard)

boomBangs :: Integral i => [i] -> [String]
boomBangs xs = do
    x <- xs
    guard (odd x)
    return (if x < 10 then "BOOM!" else "BANG!")

    This is thus a do expression [Haskell report], and as the report says, it is syntactical sugar. It is syntactical sugar for:

    boomBangs xs = xs >>= \x -> (guard (odd x) >> return (if x < 10 then "BOOM!" else "BANG!"))

    For a list the Monad instance is defined as:

    instance Monad [] where
    (>>=) = flip concatMap
    return x = [x]

    Furthermore the guard is defined as:

    guard :: Monad m => Bool -> m ()
guard True = pure ()
guard False = empty

    and the default implementation of (>>) is:

    (>>) :: Monad m => m a -> m b -> m b
(>>) u v = u >>= \_ -> v

    So the boomBangs is basically implemented as:

    boomBangs xs = concatMap (\x -> (guard (odd x) >>= \_ -> [if x < 10 then "BOOM!" else "BANG!"])) xs
             = concatMap (\x -> concatMap (\_ -> [if x < 10 then "BOOM!" else "BANG!"]) guard (odd x)) xs

    Since for a list, the guard can be specialized to:

    -- guard for the Monad []
guard :: Bool -> [()]
guard True = [()]
guard False = []

    It thus means that if the guard gets a True, it returns a singleton list, and for False an empty list. This thus means that given the guard holds, the concatMap (\_ -> [if x < 10 then "BOOM!" else "BANG!"]) will return the content in the [if x < 10 then "BOOM!" else "BANG!"], if the guard fails, it will return an empty list. The guard acts thus as some sort of filter.

    So now what is the x <-. If we look at how the do-expressions are desugared, an x <- foo, corresponds to the foo >>= \x -> ....

    For list comprehensions, x <- ... acts as some sort of "enumerator": it will enumerate over all elements in the list, and x will each time obtain one of the elements in the list to do further processing.