Думая из Пролога в Haskell - Создание списков комбинаций истина-значение

Question

Я немного знаю Пролог и только начал самостоятельное обучение в Хаскеле. Я работал над 99 Задачами для Хаскелла, многому научился и по-настоящему наслаждался Хаскеллом. Иногда я пытаюсь прояснить свое понимание проблемного пространства, кодируя что-то в Prolog, а затем размышляя о том, как это решение может относиться к функциональному подходу в Haskell. Сегодня вечером, работая над проблемами логики (проблемы 47 и 48), я отвлекся, пытаясь выполнить простую задачу по созданию списка списков всех комбинаций истинность-значение с n значениями. Я хочу функцию tValues :: Int -> [[Bool]], Эта проблема может быть решена очень простым и декларативным способом в Прологе, например:

combinations_of_n_truth_values(N, AllValues) :-
    findall(Values, n_truth_values(N, Values), AllValues).

n_truth_values(N, TruthValues) :-
    length(TruthValues, N),
    maplist(truth_value, TruthValues).

truth_value(true).
truth_value(false).

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

Я возился с некоторыми полуаналогами, используя списочные выражения, такие как следующее:

tValues:: Int -> [[Bool]]
tValues 0 = []
tValues n = [v:vs | v  <- tValue
                  , vs <- tValues (n-1) ] 

tValue :: [Bool]
tValue = [True, False]

но tValues только возвращается [], Я думаю, что мне просто нужно какое-то взаимодействие между людьми, чтобы помочь мне покачать головой и, возможно, украсить меня более глубоким пониманием.

Большое спасибо.

Answer 1

В псевдокоде, ваше понимание списка

[v:vs | v  <- tValue
      , vs <- tValues (n-1) ] 

равняется

for any combination of two elements in `tValue`  and `tValues (n-1)`
    cons the first onto the latter

Тем не мение, tValues не имеет элементов для начала, это пустой список. Давайте смоделировать это для n = 1:

tValues 1 = [v:vs | v  <- tValue
                  , vs <- tValues 0 ] 
          = [v:vs | v  <- [True, False]
                  , vs <- [] ] 
            -- since there is no vs
          = []

Это распространяется на протяжении всей рекурсии. Решение довольно простое: измените базовый вариант на пустую комбинацию:

tValues 0 = [[]] -- or: return []

Теперь симуляция дает:

tValues 1 = [v:vs | v  <- tValue
                  , vs <- tValues 0 ] 
          = [v:vs | v  <- [True, False]
                  , vs <- [[]]] 
            -- vs is []
          = [True:[],False:[]]
          = [[True],[False]]

Что именно то, что мы хотели.

Answer 2

Со списком монада,

g n = mapM (\_-> [True, False]) [1..n]

О базовом случае вашей функции. Поскольку функция возвращает список, содержащий все списки истинных значений длиныnследует, что для n=0 он должен вернуть список, содержащий все списки истинных значений длины 0, то есть список, содержащий один пустой список.

Answer 3

truths :: [[Bool]]
truths = [True] : [False] : concatMap (\bs -> [True:bs, False:bs]) truths

truthValues :: Int -> [[Bool]]
truthValues n = dropWhile ((< n) . length) . takeWhile ((<= n) . length) $ truths

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

Причина, по которой вы получаете только пустой список, заключается в том, что в конечном итоге tValues (n-1) оценивает tValues 0 что, конечно, пустой список. Попытка нарисовать из пустого списка в понимании списка приводит к сбою этой итерации. Это распространяется вверх по цепочке понимания. Измените базовый вариант на tValues 1 = [[True], [False]] и это будет работать.

Answer 4

Не полный ответ сам по себе, но, если он вас интересует, с монадой списка:

truthValues ∷ Int → [[Bool]]
truthValues 0 = return []
truthValues n = truthValues (n - 1) >>= (\l → [True:l, False:l])

или же

truthValues n = foldM (\l _ -> [True:l, False:l]) [] [1..n]

или же

truthValues = flip replicateM [True, False]

Смотрите также ответ Уилла Несс и комментарии к нему:)