Функция для генерации уникальных комбинаций списка в Haskell

Question

Существует ли функция Haskell, которая генерирует все уникальные комбинации заданной длины из списка?

Source = [1,2,3]

uniqueCombos 2 Source = [[1,2],[1,3],[2,3]]

Я пытался найти в Google, но не смог найти функцию, которая это делала специально.Перестановки не дают желаемого результата.

Кто-нибудь раньше использовал подобную функцию?

Answer 1

В lib такой операции нет, но вы можете легко реализовать ее самостоятельно:

import Data.List

main = putStrLn $ show $ myOp 2 [1, 2, 3]

myOp :: Int -> [a] -> [[a]]
myOp 0 _ = []
myOp 1 l = map (:[]) l
myOp c l = concat $ map f $ tails l
    where
        f :: [a] -> [[a]]
        f []     = []
        f (x:xs) = map (x:) $ myOp (c - 1) xs

Answer 2

Использование Data.List:

import Data.List
combinations k ns = filter ((k==).length) $ subsequences ns

Ссылка: 99 Проблемы с Haskell

В справке довольно много интересных решений, я просто выбрал краткое.

Answer 3

Я также не знаю предопределенной функции, но написать ее довольно легко:

-- Every set contains a unique empty subset.
subsets 0 _ = [[]]

-- Empty sets don't have any (non-empty) subsets.
subsets _ [] = []

-- Otherwise we're dealing with non-empty subsets of a non-empty set.
-- If the first element of the set is x, we can get subsets of size n by either:
--   - getting subsets of size n-1 of the remaining set xs and adding x to each of them
--     (those are all subsets containing x), or
--   - getting subsets of size n of the remaining set xs
--     (those are all subsets not containing x)
subsets n (x : xs) = map (x :) (subsets (n - 1) xs) ++ subsets n xs