我的 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方程,但总的来说仍然难以捉摸。

最佳答案

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

algorithm -  "Programming Pearls"中的公式-有人可以解释我吗?-LMLPHP

并为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 Falsepick E [ys] = [ys],那么这意味着∀nysxs

第二,第四和第六个等式均采用pick _ [ ] = [ ]的形式,根据mapfilter的定义,这很容易实现。

第三个方程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结束,都可以通过采用现有的ES路径并附加True来构造。等效地,每个以S结尾的路径都必须以True结尾。

第五等式同样是荒谬的,应表述为:
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)

关于algorithm - "Programming Pearls"中的公式-有人可以解释我吗?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/7967337/

10-09 18:49