P51 - 纠错码
Error correction codes
官方模块：
Problems.P51核心函数：errorCorrectingEncode,errorCorrectingDecode
题目描述
用长度为 3 的重复码编码布尔位：False 变为三个 False，True 同理。解码时对每组三位多数表决，因此每组最多一个错误仍可恢复。
函数签名
1errorCorrectingEncode :: [Bool] -> [Bool]
2errorCorrectingDecode :: [Bool] -> [Bool]
实现
方法一：replicate + 递归解码
1errorCorrectingEncode :: [Bool] -> [Bool]
2errorCorrectingEncode = concatMap (replicate 3)
3
4errorCorrectingDecode :: [Bool] -> [Bool]
5errorCorrectingDecode [] = []
6errorCorrectingDecode xs
7 | length chunk == 3 = majority chunk : errorCorrectingDecode rest
8 | otherwise = error "incomplete repetition-code block"
9 where
10 (chunk, rest) = splitAt 3 xs
11 majority bits = length (filter id bits) * 2 > length bits
编码使用 concatMap 表达“每个输入位展开成三位”，解码则按三位分组计数。不是完整码字的尾部会被拒绝，避免悄悄生成没有多数票的结果。
方法二：模式匹配 + 多数门
1errorCorrectingEncode :: [Bool] -> [Bool]
2errorCorrectingEncode [] = []
3errorCorrectingEncode (bit:bits) =
4 bit : bit : bit : errorCorrectingEncode bits
5
6errorCorrectingDecode :: [Bool] -> [Bool]
7errorCorrectingDecode [] = []
8errorCorrectingDecode (a:b:c:rest) =
9 vote a b c : errorCorrectingDecode rest
10errorCorrectingDecode _ = error "incomplete repetition-code block"
11
12vote :: Bool -> Bool -> Bool -> Bool
13vote a b c = (a && b) || (a && c) || (b && c)
这个版本直接匹配三个布尔值，用多数门表达式投票，不构造临时分组，也不计算列表长度。
方法对比
| 方法 | 特点 |
|---|---|
replicate + splitAt | 列表组合风格，容易推广到其他重复次数 |
| 模式匹配 + 多数门 | 固定三重复码，单次扫描且不构造临时列表 |
测试
1>>> errorCorrectingEncode [True, False]
2[True,True,True,False,False,False]
3>>> errorCorrectingDecode [True,True,True,False,False,False]
4[True,False]
5-- 模拟单 bit 错误：
6>>> errorCorrectingDecode [False,True,True,True,False,False]
7[True,False]
8>>> errorCorrectingDecode [True,False]
9*** Exception: incomplete repetition-code block