Implement a function like concat in Haskell without using any prelude functions

Question

Im trying to implement a function that can flatten a list of lists. only one layer deep. so if I called flatten [[3],[3, 5]] I would get [3,3,5]. this is my code:

flatten :: [[a]] -> [a]
flatten [[]] = []
flatten [(x:xs)] = 
 flatten [xs] ++ [x]

I am getting an error "non exhaustive patterns in function flatten" when I call flatten [[3], [5]]

Answer 1

There are two fundamental patterns to consider when processing a list. Any list must be either:

• the empty list ([])
• a cons cell (_:_)

Since concat acts upon a list-of-lists, we can break that second case down into two cases by pattern matching on the first element of the list, which must be either

• the empty list ([]:_)
• a cons cell ((_:_):_)¹

Which gives us three patterns all together:

concat [] = ...
concat ([]:xss) = ...
concat ((x:xs):xss) = ...

See how every list-of-lists must match exactly one of those patterns?

Now, given that breakdown, see if you can implement concat only using x, xs, xss, :, [], and concat itself.

---

1. note that (_:_):_ is a different pattern from _:_:_, which is more explictly written _:(_:_). The former is a pattern for a non-empty list at the head of a list of lists. The latter is a pattern for a list of at least two elements.

Answer 2

Possible solution:

flatten [] = []
flatten ([]:vs) = flatten vs
flatten ((x:xs):vs) = x:flatten (xs:vs)