haskell - 从 Prolog 到 Haskell 的思考——生成真值组合列表

Question

我知道一点 Prolog，并且刚刚开始在 Haskell 中进行一些自学。我一直在处理99 Problems for Haskell ，一路上学到了很多东西，真的很喜欢 Haskell。有时我试图通过在 Prolog 中编写一些代码来阐明我对问题空间的理解，然后思考该解决方案如何与 Haskell 中的函数式方法相关联。今晚，在处理有关逻辑的问题(问题 47 和 48)时，我分心了，试图完成一个简单的任务，即建立一个包含 n 个值的所有真值组合列表的列表。我想要一个函数tValues :: Int -> [[Bool]] .这个问题可以在 Prolog 中以非常直接和声明性的方式解决，例如:

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]]

这正是我们想要的。