P48 - n 元布尔函数真值表
Truth tables for n-ary boolean functions
官方模块：
Problems.P48核心函数：tablen
题目描述
把 P46 推广到 个变量。每行用前 个布尔值表示输入，最后一个布尔值表示函数结果。
函数签名
1tablen :: Int -> ([Bool] -> Bool) -> [[Bool]]
实现
方法一：递归生成赋值
1tablen :: Int -> ([Bool] -> Bool) -> [[Bool]]
2tablen n f = [xs ++ [f xs] | xs <- assignments n]
3
4assignments :: Int -> [[Bool]]
5assignments 0 = [[]]
6assignments n
7 | n < 0 = []
8 | otherwise = [x : xs | x <- [False, True], xs <- assignments (n - 1)]
用 assignments n 生成所有 组输入，然后对每组计算 并追加到末尾。
方法二：使用 replicateM
1import Control.Monad (replicateM)
2
3tablen :: Int -> ([Bool] -> Bool) -> [[Bool]]
4tablen n f
5 | n < 0 = []
6 | otherwise = [xs ++ [f xs] | xs <- replicateM n [False, True]]
replicateM n [False, True] = 从集合 {False, True} 中选取 n 个元素的所有排列，正好是二进制计数的所有组合。
方法三：用整数位运算生成
1import Data.Bits ((.&.), shiftR)
2
3tablen :: Int -> ([Bool] -> Bool) -> [[Bool]]
4tablen n f
5 | n < 0 = []
6 | otherwise = [bits i ++ [f (bits i)] | i <- [0..2^n - 1]]
7 where
8 bits :: Int -> [Bool]
9 bits i = [((i `shiftR` j) .&. 1) == 1 | j <- [n-1, n-2 .. 0]]
用整数 i 的二进制位生成每组输入。适合对位运算熟悉的读者。
方法对比
| 方法 | 代码量 | 特点 |
|---|---|---|
| 递归 assignments | ~5 行 | 自包含，不依赖外部函数 |
| replicateM | 2 行 | 最简洁，推荐 |
| 整数位运算 | 3 行 | 最抽象，适合位运算爱好者 |
测试
1>>> tablen 2 (\[a,b] -> a && b)
2[[False,False,False],[False,True,False],[True,False,False],[True,True,True]]