Как создать все возможные комбинации этих двух списков?

Question

Я хотел бы взять из этих двух списков, чтобы создать список всех комбинаций, где каждая комбинация также является списком.

Например,

Учитывая два списка: [1,2,3] и[True, False]

Комбинации:

[(1, False), (2, False), (3, False)]
[(1, False), (2, False), (3, True )]
[(1, False), (2, True ), (3, False)]
[(1, True ), (2, False), (3, False)]
[(1, False), (2, True ), (3, True )]
[(1, True ), (2, False), (3, True )]
[(1, True ), (2, True ), (3, False)]
[(1, True ), (2, True ), (3, True )]

Должно быть 2^n комбинаций, где n - это число чисел.

РЕДАКТИРОВАТЬ:

Пытался сделать следующее:

[(n, b) | n <- [1,2,3], b <- [True, False]]
(,) <$> [1,2,3] <*> [True, False]

Answer 1

Мы можем избежать использования length, что может быть небезопасно, поскольку список может иметь бесконечную длину. Используя рекурсию или шаблон сворачивания, мы избегаем этого:

{-# LANGUAGE TupleSections #-}

allComb :: [b] -> [a] -> [[(a,b)]]
allComb vs = go
    where go [] = [[]]
          go (x:xs) = (:) <$> map (x,) vs <*> go xs

или с шаблоном сворачивания в одну строку:

allComb :: [b] -> [a] -> [[(a,b)]]
allComb vs = foldr (\x -> ((:) <$> map (x,) vs <*>)) [[]]

Например:

Prelude> allComb [False, True] [1,2,3]
[[(1,False),(2,False),(3,False)],[(1,False),(2,False),(3,True)],[(1,False),(2,True),(3,False)],[(1,False),(2,True),(3,True)],[(1,True),(2,False),(3,False)],[(1,True),(2,False),(3,True)],[(1,True),(2,True),(3,False)],[(1,True),(2,True),(3,True)]]

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

Answer 2

Красиво и коротко:

traverse ((<$> [True, False]) . (,)) [1,2,3]

Или менее бессмысленно, но, возможно, более понятно:

{-# LANGUAGE TupleSections #-}

traverse (\x -> (x,) <$> [True, False]) [1,2,3]

Внутренняя функция ((<$> [True, False]) . (,) или \x -> (x,) <$> [True, False]) принимает каждый элемент таккак 1 и превращает его в [(1,True),(1,False)]. Если вы думаете о traverse f как о sequence . fmap f, то часть fmap f означает выполнение этой функции для каждой вещи в списке (получая [[(1,True),(1,False)],[(2,True),(2,False)],[(3,True),(3,False)]]), а часть sequence означает объединение их с аппликативным списком (которая моделирует недетерминизм) для создания всех возможных комбинаций (получая [[(1,True),(2,True),(3,True)],[(1,True),(2,True),(3,False)],[(1,True),(2,False),(3,True)],[(1,True),(2,False),(3,False)],[(1,False),(2,True),(3,True)],[(1,False),(2,True),(3,False)],[(1,False),(2,False),(3,True)],[(1,False),(2,False),(3,False)]]).

Answer 3

Это не может быть самым простым или наиболее эффективным ответом.

Но используя технику из Как создать список всех возможных строк от самой короткой до самой длинной , мы можем сгенерировать список всех возможных логических последовательностей. Мы берем те, которые имеют ту же длину, что и второй список, а затем объединяем их с этим списком.

allBoolPermutations :: Int -> [[Bool]]
allBoolPermutations n = takeWhile (\l -> length l == n) 
                      $ dropWhile (\l -> length l < n) 
                      $ allBools
  where
    allBools = [ c : s | s <- []:allBools, c <- [True, False]] 


zipWithBoolPermutations :: [a] -> [[(a, Bool)]]
zipWithBoolPermutations someList = map (zip someList) 
                                       (allBoolPermutations (length someList))

Тогда zipWithBoolPermutations [1,2,3] должен дать вам то, что вы хотите.

Answer 4

Ваш желаемый результат может быть получен путем определения

foo :: [a] -> [b] -> [[(a, b)]]
foo nums bools =
    map (zip nums) . sequence $ replicate (length nums) bools
  =
    let n = length nums 
    in 
        [ zip nums bs | bs <- sequence $ replicate n bools]

и вызова

foo [1,2,3] [False, True]

Этот вызов эквивалентен

    let nums = [1,2,3]
        bools = [False, True]
        n = 3
    in 
        [ zip nums bs | bs <- sequence $ replicate n bools]
      =
        [ zip [1,2,3] bs | bs <- sequence $ replicate 3 [False, True]]
      =
        [ zip [1,2,3] (b:bs) | b  <- [False, True]
                             , bs <- sequence $ replicate 2 [False, True]]
      =
        [ zip [1,2,3] (b:c:bs) | b  <- [False, True]
                               , c  <- [False, True]
                               , bs <- sequence $ replicate 1 [False, True]]
      =
        [ zip [1,2,3] (b:c:d:bs) | b  <- [False, True]
                                 , c  <- [False, True]
                                 , d  <- [False, True]
                                 , bs <- sequence $ replicate 0 [False, True] ]
      =
        [ zip [1,2,3] (b:c:d:bs) | b  <- [False, True]
                                 , c  <- [False, True]
                                 , d  <- [False, True]
                                 , bs <- sequence [] ]
      =
        [ zip [1,2,3] (b:c:d:bs) | b  <- [False, True]
                                 , c  <- [False, True]
                                 , d  <- [False, True]
                                 , bs <- [[]] ]
      =
        [ zip [1,2,3] (b:c:d:[]) | b  <- [False, True]
                                 , c  <- [False, True]
                                 , d  <- [False, True] ]

т.е.

        [ zip [1,2,3] [b,c,d]    | b  <- [False, True]
                                 , c  <- [False, True]
                                 , d  <- [False, True] ]

, и если вычислить это последнее выражение, мы также получим тот же результат.

Заполнение трех пробелов каждой возможной комбинацией двух доступных значений аналогично наличию всех возможных функций от 3 пробелов до 2значения, какими бы ни были эти пространства и значения.

Математики пишут эту функцию как 2 ³ , и действительно, мы получаем 2^3 = 8 выходных данных.

edit: комбо sequence ... replicate на самом деле просто переопределяет другое встроенное, replicateM:

foo ns bs = map (zip ns) (replicateM (length ns) bs)

, потому что replicateM n a похоже на sequence (replicate n a), но без создания промежуточного списка.

Для поклонников pointfree , таким образом, мы можем иметь

foo ns    =  map (zip ns) . replicateM (length ns)
          =  (.) ((map . zip) ns) ((replicateM . length) ns)
          =  ((.) . map . zip <*> replicateM . length)   ns

т.е.

foo       =  (.) . map . zip <*> replicateM . length