Создание списка всех возможных списков, учитывая, что каждый элемент может принимать одно из n значений

Question

В Haskell Я пытаюсь создать функцию с набором Int -> [a] -> [[a]], которая генерирует список, такой как: [[0, 0], [0, 1], [1, 0], [1, 1]], где каждый элемент в меньших списках может принимать значение 1 или 0. Каждый из меньших списков имеет тот же размер, который в данном случае равен 2. Если размер меньших списков был 3, я ожидал бы получить вывод [[0,0,0], [0,0,1], [0,1,0], [1,0,0], [1,1,0], [0,1,1], [1,0,1], [1,1,1]]

Я смотрел на permutations функция, но это не дает именно то, что я хочу. Я полагаю, что есть также функция variate, но я не могу получить доступ к этой библиотеке.

Вместо точной функции (которая также будет полезна), каков будет процесс создания такого списка?

Answer 1

Как упоминает oisdk в комментарии, более общая версия этой точной функции уже определена с именем Control.Monad.replicateM:

Prelude> import Control.Monad (replicateM)
Prelude Control.Monad> replicateM 3 [0,1]
[[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]

Answer 2

Мы можем использовать монаду списка для этого:

example :: [[Int]]
example = do
    x <- [0,1]
    y <- [0,1]
    pure [x,y]

ghci> example
[[0,0],[0,1],[1,0],[1,1]]

Играть с этим. Тогда вы сможете комбинировать его с рекурсией на n, чтобы создать нужную вам функцию.

Answer 3

Вы можете использовать функцию sequence . Как это:

 λ> 
 λ> :t sequence
sequence :: (Traversable t, Monad m) => t (m a) -> m (t a)
 λ> 
 λ> let { allLists :: Int -> [a] -> [[a]] ; allLists n xs = sequence $ replicate n xs ; }
 λ> 
 λ> allLists 3 [0,1]
[[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]
 λ> 

Answer 4

Другое определение, использующее понимание вместо карты, это

lists :: Int -> [[Int]]
lists 0 = [[]]
lists n = [x:xs | x <- [0,1], xs <- lists (n-1)] 

-- λ> lists 2
-- [[0,0],[0,1],[1,0],[1,1]]
-- λ> lists 3
-- [[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]

Answer 5

Я не уверен, что понял спецификацию, но из примеров одно возможное определение:

lists :: Int -> [[Int]]
lists 0 = [[]]
lists n = map (0:) xss ++ map (1:) xss
  where xss = lists (n-1) 

-- λ> lists 2
-- [[0,0],[0,1],[1,0],[1,1]]
-- λ> lists 3
-- [[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]