haskell, map two lists adding each element of one with each of the other list

Question 1

[ x+y | x <- xs, y <-ys ]

is the same as

do {x <- xs; y <- ys; return (x + y)}

is the same as

xs >>= \x -> ys >>= \y -> return (x + y)

>>= is called bind. What is being used here is the famous list monad. For lists, return is defined as return x = [x] and bind is defined as xs >>= f = concatMap f xs, and concatMap is, as the name suggests, simply a composition of concat and map.

The idea behind the list monad is that with x <- xs, you nondeterministically choose some arbitrary element of the list, then do some computation with it and in the end, you get a list of all the possible results you can get. So in your example,

do {x <- xs; y <- ys; return (x + y)}

chooses x and y nondeterministically from xs and ys, respectively, and you get a list of all possible results.

I will now leave it to you to use this knowledge to transform your list comprehension to an expression that uses only map and concat.

As for filter, a condition b in a list comprehensions is translated to guard b in the list monad, which can be expressed with filter if you want a non-monadic expression.

Question 2

Rather than directly giving the solution to this homework, I'll explain it in more general terms. You might not understand most of it right now, but should at least be able to pick out what you need!

map is just a specialised version (for the list functor) of the Functor method of "promoting" a function to a functor-function:

class Functor f where
  fmap :: (a->b) -> f a->f b

Now, lists are a particularly powerful kind of functor: an applicative functor, even a monad. Applicative confuses many programmers, but your example is a really good fit:

Prelude> :m +Control.Applicative
Prelude Control.Applicative> let f1 xs ys = (+) <‌$> xs <‌*> ys
Prelude Control.Applicative> :t f1
f1 :: (Num b, Applicative f) => f b -> f b -> f b
Prelude Control.Applicative> f1 [1,2,3,4] [5,6,7,8]
[6,7,8,9,7,8,9,10,8,9,10,11,9,10,11,12]

Of course you could also write simply

Prelude Control.Applicative> (+) <‌$> [1,2,3,4] <*> [5,6,7,8]
[6,7,8,9,7,8,9,10,8,9,10,11,9,10,11,12]

Looks simple enough, but how does this work? What's confusing about the Applicative class is that you keep plunging curried functions into the functor, evaluate them partially in there, and somehow retrieve the result from outside. With monad's you don't do that, so they're a bit simpler to grasp. Using only the Monad type class, the example can also be done (Monad is strictly sronger than Applicative).

Haskell lists comprehensions are really just syntactic sugar for monad operations!

                   [ x+y | x <- xs, y <- ys ]

is sugar for

                   xs >>= \x -> ys >>= \y -> return (x+y)

or with extra parentheses:

                   xs >>= ( \x -> ( ys >>= ( \y -> return (x+y) ) ) )

well, this you can transform to something with only map and concat by using these rules:

ys >>= (\y -> return (f y)) is the same as map f ys.
zs >>= (\z -> g z) is the same as concat (map g zs).

Question 3

One way would be this:

f1 xs ys = concat $ map (\x -> map (\y -> x + y) ys) xs

Demo in ghci:

λ> f1 [1,2,3,4] [5,6,7,8]
[6,7,8,9,7,8,9,10,8,9,10,11,9,10,11,12]

Question 4

A generic list comprehension has the form

[ e | qual1 , qual2 , ... , qualN ]

where e is an expression, and qual are qualifiers. Qualifiers can be of three forms: generators (x<-list), boolean guards (x/=0), and local declarations (let x = ... ). Since you only use generators, I will focus on those.

According to the Haskell definition, list comprehesions can be translated as follows

[ e | x<-l , quals ] = concat $ map (\x -> [ e | quals ]) l
[ e | ]              = [ e ]  -- singleton list

so you can apply these to [ x+y | x <- xs, y <-ys ] and obtain the solution (which is essentially the one in Sibi's answer).