algorithm - 来自 "Programming Pearls"的方程式 - 有人可以解释一下吗？

Question

friend 们，我感觉自己被困住了。有人能解释一下我从“功能算法设计的珍珠”第 11 章(“不是最大段和”)中选择方程式吗？

这是问题(稍微简化了一点) 让我们有一些具有给定转换的状态:

data State = E | S | M | N 
                deriving (Show, Eq) 

step E False = E 
step E True = S 
step S False = M 
step S True = S 
step M False = M 
step M True = N 
step N False = N 
step N True = N 

现在，让我们定义选择:

 pick q = map snd . filter ((== q) . fst) . map (\a -> (foldl step E a, a))

作者声称以下七个方程式成立:

pick E xs = [[]]
pick S [ ] = [ ]
pick S (xs ++ [x]) = map (++[x ]) (pick S xs ++ pick E xs)
pick M [ ] = [ ]
pick M (xs ++ [x ]) = pick M xs ++ pick S xs
pick N [ ] = [ ]
pick N (xs ++ [x]) = pick N xs ++ map (++[x]) (pick N xs ++ pick M xs)

有人能用简单的话向我解释一下，为什么这些等式是正确的，我们如何证明一个明显的证据？我觉得我几乎理解了 S 方程，但总的来说这仍然是难以捉摸的。

Answer 1

好的，我需要可视化您的状态图:

并为 pick::State -> [[Bool]] -> [(State, [Bool]) 提供类型签名。

现在，这与您的第一个等式 pick E xs = [[]] 不一致 - 它必须是 pick E xs = [(E,[]) ]。

也许你打算这样定义pick:

pick :: State -> [[Bool]] -> [[Bool]]
pick q = map snd . filter ((== q) . fst) . map (\a -> (foldl step E a, a))

假设该定义，第一个等式现在就有意义了。它声称如果您从 E 开始，xs 中唯一将以 E 结束的 bool 值序列是空列表。

请注意，这假设 [] ∈ xs。

此外，如果 ys = replicate n False，pick E [ys] = [ys]，那么这意味着∀ n， ys ∉ xs.

第二个、第四个和第六个等式都是 pick _ [ ] = [ ] 的形式，根据 map 和 的定义，这很简单>过滤器。

第三个等式，pick S (xs++ [x]) = map (++[x ]) (pick S xs++ pick E xs) 也没有什么意义.我猜它想表达的意思是:

pick S (map (++[True] xs) = map (++[True]) (pick S xs ++ pick E xs)

也就是说 - 任何从 E 开始到 S 结束的路径都可以通过采用到 E 或 的现有路径来构造code>S 并附加 True。同样，以 S 结尾的每条路径都必须以 True 结尾。

第五个等式同样 absurd ，应该表述为:

pick S (map (++[False] xs) = map (++[False]) (pick S xs ++ pick M xs)

第七个等式应该重述为:

pick N (map (++ [True]) xs) = pick N xs ++ map (++[True]) (pick N xs ++ pick M xs)