生成任意长度haskell的真值表 [英] Generate a truth table of arbitrary length haskell

问题描述

 组合:: 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]] 
  

我可以做一个列表理解：

 组合n = [[a，b] | a<  -  [True，False]，b<  -  [True，False]] 
  

不针对任意数字进行缩放。

您可以给我一个提示吗？

解决方案

@chi的答案，这是一个实现函数的递归方式。我已经将它重新命名为真相：

 真相:: 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））
  

在这里我们简单地附加一个true / false值赋给先前结果中的每个元素。我只在GHCi中试过这个解决方案，它计算真理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] 
  

for an assignment I have to generate a truth table like this:

combinations :: Int -> [[Bool]]

combinations 3 should output:

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

I can do a list comprehension:

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

but that doesn't scale for arbitrary numbers.

Could you please give me a hint?

解决方案

Adding to @chi 's answer, here's a recursive way of implementing the function. I've renamed it to a snappier truths:

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

those last 3 lines could be rewritten as

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

Here we simply append a true/false value to each element in the previous result. The only edge case would be for negative numbers, but you can probably work that out yourself.

I tried this solution out in GHCi, it computes truths 10 in about 0.6 seconds, which is impressive, considering there are 1024 lists, each containing 10 elements.

I also came up with another, more interesting version using sequence from Control.Monad:

import Control.Monad (sequence)

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

this will produce the same output. Note that it could also be rewritten in a points-free style as such, to the same effect:

truths = sequence . flip replicate [True,False]

这篇关于生成任意长度haskell的真值表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！