Расчески на большом наборе не вычисляют Haskell

Чтобы извлечь i элементы из x:xs, вы можете действовать двумя способами:

• вы сохраняете x и извлекаете только i-1 элементов из xs
• вы отбрасываете x и извлекаете все элементы i из xs

Следовательно, решение:

comb :: Int -> [a] -> [[a]]
comb 0 _      = [[]]  -- only the empty list has 0 elements
comb _ []     = []    -- can not extract > 0 elements from []
comb i (x:xs) = [ x:ys | ys <- comb (i-1) xs ]  -- keep x case
                ++ comb i xs                    -- discard x case

Кстати, приведенный выше код также «доказывает» известную рекурсивную формулу для биномиальных коэффициентов. Возможно, вы уже встречали эту формулу, если посещали занятия по математическому анализу. Полагая B(k,n) = length (comb k [1..n]), имеем

B(k+1,n+1) == B(k,n) + B(k+1,n)

что является прямым следствием последней строки кода выше.

Прямо сейчас немного сложно понять, что вы пытаетесь сделать, но я думаю, что у вас есть проблемы в том, что вы будете фильтровать и отображать много.

Я думаю, что простой способ получить то, что вам нужно, это:

module Combinations where

import Data.List (delete)

combs :: Eq a => Int -> [a] -> [[a]]
combs 0 _ = [[]]
combs i xs = [ y:ys | y <- xs, ys <- combs (i-1) (delete y xs) ]

который использует delete из Data.List

Нужно быть достаточно ленивым, чтобы быстро находить вам комбинации - конечно, все это займет некоторое время ;)

λ> take 5 $ combs 5 [1..52]
[[1,2,3,4,5],[1,2,3,4,6],[1,2,3,4,7],[1,2,3,4,8],[1,2,3,4,9]]

как это работает

это один из тех рекурсивных комбинаторных алгоритмов, который работает, выбирая первую карту y из всех карт xs, а затем рекурсивно gets the rest of the handysfrom the deck without the selected carddelete xsand then putting it back togethery:ys` внутри монады списка (здесь с использованием списков).

Кстати: таких колод 311 875 200 ;)

версия без списков-включений

вот версия без понимания на случай, если у вашей системы есть проблемы здесь:

combs :: Eq a => Int -> [a] -> [[a]]
combs 0 _ = [[]]
combs i xs = do
  y <- xs
  ys <- combs (i-1) (delete y xs)
  return $ y:ys

версия, которая удалит перестановки

этот использует Ord для получения сортировки элементов в порядке возрастания и при этом удаляет дубликаты в отношении перестановки - для этого ожидается, что xs будет предварительно отсортирован!

Примечание. Версия chi работает с меньшим количеством ограничений и может быть более преформной, но я думаю, что это красиво и читабельно, и хорошо сочетается с предыдущей версией, поэтому, возможно, она вас заинтересует.

Я знаю, что это не часто делается в Haskell/FP, где вы боретесь за самые общие и абстрактные случаи, но я пришел из среды, где большинство стремится к удобочитаемости и пониманию (кодирование для программиста, а не только для компилятора) - так что будьте осторожны ;)

combs' :: Ord a => Int -> [a] -> [[a]]
combs' 0 _  = [[]]
combs' i xs = [ y:ys | y <- xs, ys <- combs' (i-1) (filter (> y) xs) ]