ConcatMap in haskell without ++

Question

I'm trying to write the code for Haskell concatmap without using the ++ operator where

concatMap :: (a -> [b]) -> [a] -> [b]

and producing the same result of

concatMap f = foldr ((++) . f) []

I'm quite new to Haskell and this was just an exercise I found. Actually, I do not even know if this can be done.

Answer 1

Here's a way that makes the state of the computation explicit:

concatMap :: (a -> [b]) -> [a] -> [b]
concatMap f = go []
  where
    -- We have b values; use one.
    go (b:bs) as = b : go bs as
    -- No bs left; get some more.
    go [] (a:as) = go (f a) as
    -- Nothing left; we're done.
    go [] [] = []

This maintains the current list of bs, filling it up whenever it's empty.

Answer 2

This might be cheating, but how about:

myConcatMap f s = concat (map f s)

The concat function uses some sort of ++ in its source code, so that is why you might not like it. You can try to use an alternative concat that does list comprehensions, it has a more "from scratch" feeling.

myconcat ll = [y | x <- ll, y <- x]

Answer 3

You can use the fact that foldr (:) = flip (++)

concatMap f = foldr (flip (foldr (:)) . f) []

Or pointfree:

concatMap = flip foldr [] . (flip (foldr (:)) .)