はわわーっ

はわわわわっ

haskell でグループ分け

9人を2,3,4人のグループに分ける方法が何通りあるか、みたいなやつ。

> group [2,3,4] "abcdefghi"
["ab","cde","fghi"],["ab","cdf","eghi"],["ab","cdg","efhi"], ... ]

まず、グループから n 人を選ぶ関数 combinations を作る。選んだ n 人と残りをタプルで返すことにする。

combinations :: Int -> [a] -> [([a], [a])]
combinations 0 xs     = [([], xs)]
combinations _ []     = []
combinations n (x:xs) = [(x:ys, zs) | (ys, zs) <- combinations (n-1) xs] ++
                        [(ys, x:zs) | (ys, zs) <- combinations n xs]

で、これを使ってグループ分けの関数を作る。

group :: [Int] -> [a] -> [[[a]]]
group [] _      = [[]]
group (n:ns) xs = [g:gs | (g, rs) <- combinations n xs, gs <- group ns rs]

リスト内包表記を使わないなら

group :: [Int] -> [a] -> [[[a]]]
group [] _ = [[]]
group (n:ns) xs = concatMap groupHelper $ combinations n xs
  where
    groupHelper (xs, ys) = map (xs:) $ group ns ys

こんな感じ。更に短く書くと

group [] = const [[]]
group (n:ns) = concatMap (uncurry $ (. group ns) . map . (:)) . combinations n

こうも書ける。ここまでやると何がなんだかわからないですね。