Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is `group list by size` a fold?

Tags:

haskell

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))
like image 952
mb14 Avatar asked Oct 04 '14 08:10

mb14


1 Answers

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.

like image 70
GS - Apologise to Monica Avatar answered Oct 04 '22 22:10

GS - Apologise to Monica