Разделение списка довольно

Question

Я уверен, что это довольно распространенная вещь, но я ничего не могу найти (мой интернет-поиск-фу не силен).

У меня есть функция, которая может группа списка в списке списков N элементов, каждый с окончательным подсписка будучи меньше, чем N, если длина списка не делится на N. Некоторые примеры:

groupEvery 2 [1,2,3,4]    = [[1,2],[3,4]] 
groupEvery 4 [1,2,3,4,5,6,7,8,9,10] = [[1,2,3,4], [5,6,7,8], [9,10]] 

То, что я хочу, чтобы взять список и положительное целое число п (в приведенных выше примерах п можно было бы сказать, что 2 и 3) и разделить его в новый список п списков. Он должен работать над списком любого типа и производить подсписок, размеры которых отличаются как можно меньше.

Так что я хотел бы иметь:

fairPartition 3 [1,2,3,4,5,6,7,8,9,10] = [[1,2,3,4], [5,6,7], [8,9,10]] 

Или любая комбинация подсписков до тех пор, как существуют две длины 3 и один длины 4.

наивная попытка с помощью groupEvery:

fairPartition :: Int -> [a] -> [[a]] 
fairPartition n xs = groupEvery ((length xs `div` n) + 1) xs 

fairPartition 4 [1..10] = [[1,2,3],[4,5,6],[7,8,9],[10]] 

но, как вы можете видеть (3,3,3,1), не является справедливым распределением длин, а для списков меньшей длины он даже не возвращает правильное количество подписок:

# Haskell, at GHCi 
*Main> let size = 4 in map (\l -> length . fairPartition 4 $ [1..l]) [size..25] 
[2,3,3,4,3,3,4,4,3,4,4,4,4,4,4,4,4,4,4,4,4,4] 

Мне нужна функция {псевдо, фактическая} -код или объяснение, которое легко перевести на Haskell (перевод идентичности был бы лучшим!).

Спасибо.

Answer 1

Вы можете использовать функцию splitsplitPlaces для этого.

import Data.List.Split 

fairPartition n xs = case length xs `quotRem` n of 
    (q, r) -> splitPlaces (replicate r (q+1) ++ replicate (n-r) q) xs