CODEWITHSUNDEEP
haskell
mb14
mb14

Reputation: 22616

Is `group list by size` a fold?

I came across this problem : grouping the elements of a list by packet of the same size, so that

> groupBy 3 [1..10] 
[[1,2,3], [4,5,6], [7,8,9], [10]]

Nothing really hard to do, but first I was surprise that I couldn't find a function for it. My first try was

 groupBy _ [] = []
 groupBy n xs = g : groupBy n gs
              where (g, gs) = splitAt n xs

So far so good, it works, even on infinite list. However I don't like the first line groupBy _ [] = []. Seems a good candidate for a fold but I couldn't figure it out.

So can this function can be written as a fold or as a one liner ?

Update

My attempt at a one liner:

groupBy' n l = map (map snd) $ groupBy ((==) `on` fst) $ concatMap (replicate n) [1..] `zip` l

It took me 10 times more to write that the initial attempt.

Update 2

Following Ganesh answer and using unfoldr and the help of pointfree I came out with this convoluted point free solution

groupBy' n = unfoldr $ listToMaybe . (ap (>>) (return.splitAt n))

Upvotes: 6

Views: 246

Answers (1)

Ganesh Sittampalam
Ganesh Sittampalam

Reputation: 29110

You can do it as a fold with some gymnastics, but it's much nicer as an unfold:

 unfoldr (\xs -> if null xs then Nothing else Just (splitAt n xs))

[You'll need to import Data.List if you haven't already]

The type of unfoldr is:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

The idea of unfoldr is that a generating function decides whether to stop (Nothing) or keep going (Just). If the result is Just then the first element of the tuple is the next element of the output list, and the second element is passed to the generating function again.

As @leftroundabout pointed out in a comment on the question, an unfold is much more natural here because it treats the output list elements as similar to each other, whereas in a fold the input list elements should be treated similarly. In this case the need to start a new sublist every n elements of the input list makes this harder.

Upvotes: 8

Related Questions