Сформировать таблицу истинности произвольной длиной Haskell

Question

для назначения я должен создать таблицу истинности так:

combinations :: Int -> [[Bool]] 

комбинацию 3 следует выход:

[[False, False, False],[False, False, True],[False, True, False],[False, True, True][True, False, False][True, False, True],[True, True, False],[True, True, True]] 

я могу сделать список понимание:

combinations n = [[a,b] | a<-[True, False], b <-[True, False]] 

но это не масштабируется для любых чисел.

Не могли бы вы дать мне подсказку?

Answer 1

Добавляя к ответу @chi, здесь рекурсивный способ реализации функции. Я переименовал его к мгновенным truths:

truths :: Int -> [[Bool]] 
truths 0 = [[]] 
truths n = do 
    b <- [True,False] 
    map (b :) (truths (n - 1)) 

эти последние 3 строки можно переписать в виде

truths n = [True,False] >>= \b -> map (b :) (truths (n - 1)) 

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

Я пробовал это решение в GHCi, он вычисляет truths 10 примерно за 0,6 секунды, что впечатляет, учитывая, что в списке 1024 человека содержится 10 элементов.

я придумал другую, более интересную версию, используя sequence из Control.Monad:

import Control.Monad (sequence) 

truths :: Int -> [[Bool]] 
truths n = sequence (replicate n [True,False]) 

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

truths = sequence . flip replicate [True,False] 

Answer 2

Вы должны рассуждать рекурсивно.

Для создания комбинаций n вы можете действовать следующим образом. Сначала сгенерируйте все комбинации n-1: назовите этот список c (это список списков логических элементов). Затем для каждого элемента xs из c (здесь xs - это список булевых), сгенерируйте x:xs, где x является произвольным булевым. Обращайтесь с корпусом n=0 специально, чтобы обеспечить базовый корпус.