Декартово произведение, приводящее к списку списков фиксированной длины (способ haskell)

Я хочу создать последовательность элементов ([0, 1]) фиксированной длины (например, 4), чтобы она приводила к списку списков элементов, содержащих все комбинации [0,1].

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

Prelude > let base = [1, 0]
Prelude > [[x0, x1, x2, x3] | x0 <- base, x1 <- base, x2 <- base, x3 <- base]
[[1,1,1,1],[1,1,1,0],[1,1,0,1], ... [0,0,0,0]]

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

Каков идиоматический способ сделать это?


haskell
person Robin    schedule 02.07.2015    source источник

Ответы (1)


arrow_upward
7
arrow_downward

sequence работает:

Prelude> sequence (replicate 4 [1,0])
[[1,1,1,1],[1,1,1,0],[1,1,0,1],[1,1,0,0],[1,0,1,1],[1,0,1,0],[1,0,0,1],[1,0,0,0],[0,1,1,1],[0,1,1,0],[0,1,0,1],[0,1,0,0],[0,0,1,1],[0,0,1,0],[0,0,0,1],[0,0,0,0]]

Но сочетание последовательности и реплики уже имеет название:

Prelude> import Control.Monad
Prelude Control.Monad> replicateM 4 [1,0]
[[1,1,1,1],[1,1,1,0],[1,1,0,1],[1,1,0,0],[1,0,1,1],[1,0,1,0],[1,0,0,1],[1,0,0,0],[0,1,1,1],[0,1,1,0],[0,1,0,1],[0,1,0,0],[0,0,1,1],[0,0,1,0],[0,0,0,1],[0,0,0,0]]

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

sequence :: Monad m => [m a] -> m [a]
sequence [] = return []
sequence (x:xs) = do
    x'  <- x
    xs' <- sequence xs
    return (x':xs')

(Есть более короткие способы написать это, но это самый простой.)

Оказывается, sequence тоже не содержит никакой интересной логики. Это единственная очевидная функция с такой сигнатурой типа, которая использует весь свой аргумент. Так что настоящая магия должна быть в экземпляре Monad для [], я думаю.

instance Monad [] where
    return x = [x]
    xs >>= f = concatMap f xs

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

concatMap :: (a -> [b]) -> [a] -> [b]
concatMap _ [] = []
concatMap f (x:xs) = f x ++ concatMap f xs

Я не уверен, насколько все это помогает, но об этом стоит помнить.

Возможно, более полезным будет специализировать сигнатуру типа от sequence до m ~ []:

sequence :: [[a]] -> [[a]]

В данном конкретном случае sequence лучше было бы переименовать в sequences. Он создает все последовательности, состоящие из выбора одного элемента из каждого внутреннего списка.

person Carl    schedule 02.07.2015
comment
Ха, я знал, что есть способ Haskell, спасибо! Не могли бы вы также сказать мне, почему нам нужна монада здесь? - person Robin; 02.07.2015
comment
@Robin Ну, [] уже является экземпляром Monad. Трудно решить проблему списка без списков. Что касается импорта Control.Monad, это просто потому, что там хранится replicateM. - person Carl; 02.07.2015
comment
благодарю вас. Кажется, мне нужно прочитать еще несколько глав о монадах. - person Robin; 02.07.2015