import Data.Maybe

-- | Trie aは[[a]]の別表現、共通のプレフィックスを括り出した形
type Trie a = [Branch a]
data Branch a = Empty | Cons a (Trie a)

-- | Trie表現からリスト表現ヘ変換
interpret :: Trie a -> [[a]]
interpret = concatMap f
  where
    f Empty = [[]]
    f (Cons hd trie) = do
      tl <- interpret trie
      return $ hd : tl

example :: [[Int]]
example = interpret $ [Cons 1 [Empty, Cons 2 [Empty]]]
  -- [[1], [1,2]]

-- | Trieを返すpowerset。
-- interpret (powersetT xs) == powerset xs
powersetT :: [a] -> Trie a
powersetT [] = [Empty]
powersetT (x:xs) = Cons x other : other
  where other = powersetT xs

-- | 長さnの要素のみを取る。nより深い部分は評価しない
-- interpret (takeJustT n xs) == filter ((==n) . length) (interpret xs)
takeJustT :: Int -> Trie a -> Trie a
takeJustT 0 = filter isEmpty
  where
    isEmpty Empty = True
    isEmpty Cons{} = False
takeJustT n = mapMaybe f
  where
    f Empty = Nothing
    f (Cons hd tl) = Just $ Cons hd (takeJustT (n-1) tl)

-- | Trieを返すcombinations。
combinationsT :: Int -> [a] -> Trie a
combinationsT n xs = takeJustT n $ powersetT xs

combinations :: Int -> [a] -> [[a]]
combinations n xs = interpret $ combinationsT n xs

main = print $ combinations 2 [1..100] -- すぐ終わる