CODEWITHSUNDEEP
haskell
Kert Kukk
Kert Kukk

Reputation: 715

Can haskell grouping function be made similarly like that?

Is it possible to somehow make group function similarly to that:

group :: [Int] -> [[Int]]
group [] = []
group (x:[]) = [[x]]
group (x:y:ys)
    | x == y = [[x,y], ys]
    | otherwise = [[x],[y], ys]

Result shoult be something like that:

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

PS: I already looked for Data.List implementation, but it doesn't help me much. (https://hackage.haskell.org/package/base-4.3.1.0/docs/src/Data-List.html)

Is it possible to make group funtion more clearer than the Data.List implementation?

Or can somebody easily explain the Data.List implementation atleast?

Upvotes: 1

Views: 3143

Answers (4)

Sean
Sean

Reputation: 11

Here, I come up with a solution with foldr:

helper x [] = [[x]]
helper x xall@(xs:xss) 
   | x == head xs = (x:xs):xss
   | otherwise = [x]:xall

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

Upvotes: 0

chepner
chepner

Reputation: 530960

Another way of looking at this is to take the first element x of the input and recursively group the rest of it. x will then either be prepended to the first element of the grouping, or go in a new first group by itself. Some examples:

  1. With [1,2,3], we'll add 1 to a new group in [[2], [3]], yielding [[1], [2], [3]]
  2. With [1,1,2], we'll add the first 1 to the first group of [[1], [2]], yielding [[1,1], [2]].

The resulting code:

group :: [Int] -> [[Int]]
group [] = []
group [x] = [[x]]
group (x:y:ys) = let (first:rest) = group (y:ys)
                 in if x /= y
                    then [x]:first:rest -- Example 1 above
                    else (x:first):rest -- Example 2 above

IMO, this simplifies the recursive case greatly by treating singleton lists explicitly.

Upvotes: 1

Michael
Michael

Reputation: 2909

Your idea is good, but I think you will need to define an ancillary function -- something like group_loop below -- to store the accumulated group. (A similar device is needed to define span, which the Data.List implementation uses; it is no more complicated to define group directly, as you wanted to do.) You are basically planning to move along the original list, adding items to the subgroup as long as they match, but starting a new subgroup when something doesn't match:

group [] = []
group (x:xs) = group_loop [x] x xs
  where
  group_loop acc c [] = [acc]
  group_loop acc c (y:ys) 
   | y == c    = group_loop (acc ++ [y]) c ys
   | otherwise = acc : group_loop [y] y ys

It might be better to accumulate the subgroups by prepending the new element, and then reversing all at once:

group [] = []
group (x:xs) = group_loop [x] x xs
  where
  group_loop acc c [] = [reverse acc]
  group_loop acc c (y:ys) 
   | y == c    = group_loop (y:acc) c ys
   | otherwise = reverse acc : group_loop [y] y ys

since then you don't have to keep retraversing the accumulated subgroup to tack things on the end. Either way, I get

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

Upvotes: 2

Chad Gilbert
Chad Gilbert

Reputation: 36375

group from Data.List is a specialized version of groupBy which uses the equality operator == as the function by which it groups elements.

The groupBy function is defined like this:

groupBy                 :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy _  []           =  []
groupBy eq (x:xs)       =  (x:ys) : groupBy eq zs
                           where (ys,zs) = span (eq x) xs

It relies on another function call span which splits a list into a tuple of two lists based on a function applied to each element of the list. The documentation for span includes this note which may help understand its utility.

span p xs is equivalent to (takeWhile p xs, dropWhile p xs)

Make sure you first understand span. Play around with it a little in the REPL.

Ok, so now back to groupBy. It uses span to split up a list, using the comparison function you pass in. That function is in eq, and in the case of the group function, it is ==. In this case, the span function splits the list into two lists: The first of which matches the first element pulled from the list, and the remainder in the second element of the tuple.

And since groupBy recursively calls itself, it appends the rest of the results from span down the line until it reaches the end.

Visually, you can think of the values produced by span looking something like this:

([1], [2,2,3,3,3,4,1,1])
([2,2], [3,3,3,4,1,1])
([3,3,3], [4,1,1])
([4], [1,1])
([1,1], [])

The recursive portion joins all the first elements of those lists together in another list, giving you the result of 

[[1],[2,2],[3,3,3],[4],[1,1]]

Upvotes: 2

Related Questions