Implementing List#flatten in Haskell

Question

Scala offers a List#flatten method for going from List[Option[A]] to List[A].

scala> val list = List(Some(10), None)
list: List[Option[Int]] = List(Some(10), None)

scala> list.flatten
res11: List[Int] = List(10)

I attempted to implement it in Haskell:

flatten :: [Maybe a] -> [a]
flatten xs = map g $ xs >>= f

f :: Maybe a -> [Maybe a]
f x = case x of Just _  -> [x]
                Nothing -> []

-- partial function!
g :: Maybe a -> a
g (Just x) = x

However I don't like the fact that g is a partial, i.e. non-total, function.

Is there a total way to write such flatten function?

Answer 1

Your flatten is the same as catMaybes (link) which is defined like this:

catMaybes :: [Maybe a] -> [a]
catMaybes ls = [x | Just x <- ls]

The special syntax Just x <- ls in a list comprehension means to draw an element from ls and discard it if it is not a Just. Otherwise assign x by pattern matching the value against Just x.

Answer 2

A slight modification of the code you have will do the trick:

flatten :: [Maybe a] -> [a]
flatten xs = xs >>= f

f :: Maybe a -> [a]
f x = case x of Just j  -> [j]
                Nothing -> []

If we extract the value inside of the Just constructor in f, we avoid g altogether.

Incidentally, f already exists as maybeToList and flatten is called catMaybes, both in Data.Maybe.