从Prolog和Haskell中思考 - 生成真值组合列表

Question

我知道一些Prolog,刚开始在Haskell做一些自学.我一直在努力解决Haskell的99个问题,一路上学习并真正享受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]]

这正是我们想要的.

Answer 2

随着列表monad,

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

关于你的功能的基本情况.当函数返回一个包含所有真值列表长度的列表时n,它n=0会返回一个列表,其中包含长度为0的所有真值列表,即包含一个空列表的列表.