CODEWITHSUNDEEP
haskell
Ben mckenzie
Ben mckenzie

Reputation: 85

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

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]]

Upvotes: 3

Views: 8142

Answers (4)

PSS
PSS

Reputation: 6111

You can implement it exactly the same way concat is implemented in Prelude:

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

Upvotes: 0

Nyavro
Nyavro

Reputation: 8866

Possible solution:

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

Upvotes: 3

rampion
rampion

Reputation: 89073

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 ((_:_):_)1

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.

Upvotes: 10

Alexander VoidEx Ruchkin
Alexander VoidEx Ruchkin

Reputation: 444

You are using incorrect patterns. [smth] matches list with one element, in your case:

[[]] - is list with one empty list [(x:xs)] - is list with one element - list (x:xs), which is not empty

So both cases matches single-element list. That's why function fails on [[3], [5]]

Obviously, you may wanted other two cases: empty ([]) and not empty list ((x:xs))

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

Upvotes: 0

Related Questions