Haskell - Group list elements with foldr function

Question

This is for an assignment in Haskell. We have been tasked with defining various functions using the foldr function.

We have been given a type:

group :: Eq a => [a] -> [[a]]

and been asked to define it such that:

group [1,2,2,3,4,4,4,5] = [[1], [2,2], [3], [4,4,4], [5]]
group [1,2,2,3,4,4,4,5,1,1,1] = [[1], [2,2], [3], [4,4,4], [5], [1,1,1]]

This is what I have so far:

group = foldr (\x xs -> if x == head (head xs) then (x : head xs) : xs else (x : []) : (head xs) : xs )

But when I try to load this into ghci interpreter I get the following error message:

Couldn't match type `[a0] -> [a]' with `[[a]]'
Expected type: [a] -> [[a]]
  Actual type: [a] -> [a0] -> [a]
In the return type of a call of `foldr'
Probable cause: `foldr' is applied to too few arguments
In the expression:
  foldr
    (\ x xs
       -> if x == head (head xs) then
              (x : head xs) : xs
          else
              (x : []) : (head xs) : xs)
In an equation for `group':
    group
      = foldr
          (\ x xs
             -> if x == head (head xs) then
                    (x : head xs) : xs
                else
                    (x : []) : (head xs) : xs)

If anyone could explain any reasons why my code isn't working as I expect it to, that would be greatly appreciated. Thanks.

Answer 1

I think you are on the right track so I'll try to write your idea a bit nicer. What I want to say is this: you should pull out the first argument of foldr into an function and do pattern-matching again:

group :: Eq a => [a] -> [[a]]
group = foldr f undefined
  where f x []        = undefined
        f x (ys@(y:_):yss)
          | x == y    = undefined
          | otherwise = undefined

this should do - now you only have to put in the right stuff where I put undefined :)

I'll come back later and finish it

---

well I guess you gave up or something - anyway here is one solution:

group :: Eq a => [a] -> [[a]]
group = foldr f []
  where f x []        = [[x]]
        f x (ys@(y:_):yss)
          | x == y     = (x:ys):yss
          | otherwise = [x]:ys:yss

and a few examples:

λ> group []
[]
λ> group [1]
[[1]]
λ> group [1,1]
[[1,1]]
λ> group [1,2,1]
[[1],[2],[1]]
λ> group [1,2,2,3,4,4,4,5]
[[1],[2,2],[3],[4,4,4],[5]]

note that fs patterns are not exhaustive (which is no problem - think about why) - of course you can extent it if you want (and if you don't agree with group [] = [] than you have to.

Answer 2

Just to mention that if I am not wrong, this is the problem 9 from the 99 haskell problems that can be found here: https://wiki.haskell.org/99_questions/
For every problem, it has a bunch of solutions(usually) and since Carsten presented a great solution, you can go there and see other solutions so you can get different ideas on how the same thing can be achieved in various ways!