haskell - 查找非穷举模式

Question

我能以某种方式看到haskell试图使用什么模式吗？它适用于较小的示例，但在较大的示例上崩溃，我很难找到它可能是什么情况。

euler18 :: [[Integer]]
euler18 = pathPyr minipyr

pathPyr xss = path [(head xss)] (tail xss)

minipyr = [[3],[7,4],[2,4,6]]
pyramid = [[75], [95,64], [17,47,82], [18,35,87,10], [20,4,82,47,65], [19,1,23,75,3,34], [88,2,77,73,7,63,67], [99,65,4,28,6,16,70,92], [41,41,26,56,83,40,80,70,33], [41,48,72,33,47,32,37,16,94,29], [53,71,44,65,25,43,91,52,97,51,14], [70,11,33,28,77,73,17,78,39,68,17,57], [91,71,52,38,17,14,91,43,58,50,27,29,48], [63,66,4,68,89,53,67,30,73,16,69,87,40,31], [4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]]

path :: [[Integer]] -> [[Integer]] -> [[Integer]]
path xss (ys:[])  = extendpath xss ys
path xss (ys:yss) = path (extendpath xss ys) yss

extendpath :: [[Integer]] -> [Integer] -> [[Integer]]
extendpath (xs:[]) (y1:y2:[]) = [y1:xs,y2:xs]
extendpath (xs:xss) (y1:y2:ys) = [y1:xs,y2:xs] ++ extendpath xss (y2:ys)

输出：

*Main> pathPyr pyramid 
[[4,63,91,70,53,41,41,99,88,19,20,18,17,95,75],[62,63,91,70,53,41,41,99,88,19,20,18,17,95,75],[62,66,91,70,53,41,41,99,88,19,20,18,17,95,75],[98,66,91,70,53,41,41,99,88,19,20,18,17,95,75],[98,66,71,70,53,41,41,99,88,19,20,18,17,95,75],[27,66,71,70,53,41,41,99,88,19,20,18,17,95,75],[27,4,71,70,53,41,41,99,88,19,20,18,17,95,75],[23,4,71,70,53,41,41,99,88,19,20,18,17,95,75],[23,4,71,11,53,41,41,99,88,19,20,18,17,95,75],[9,4,71,11,53,41,41,99,88,19,20,18,17,95,75],[9,68,71,11,53,41,41,99,88,19,20,18,17,95,75],[70,68,71,11,53,41,41,99,88,19,20,18,17,95,75],[70,68,52,11,53,41,41,99,88,19,20,18,17,95,75],[98,68,52,11,53,41,41,99,88,19,20,18,17,95,75],[98,89,52,11,53,41,41,99,88,19,20,18,17,95,75],[73,89,52,11,53,41,41,99,88,19,20,18,17,95,75],[73,89,52,11,71,41,41,99,88,19,20,18,17,95,75],[93,89,52,11,71,41,41,99,88,19,20,18,17,95,75],[93,53,52,11,71,41,41,99,88,19,20,18,17,95,75],[38,53,52,11,71,41,41,99,88,19,20,18,17,95,75],[38,53,38,11,71,41,41,99,88,19,20,18,17,95,75],[53,53,38,11,71,41,41,99,88,19,20,18,17,95,75],[53,67,38,11,71,41,41,99,88,19,20,18,17,95,75],[60,67,38,11,71,41,41,99,88,19,20,18,17,95,75],[60,67,38,33,71,41,41,99,88,19,20,18,17,95,75],[4,67,38,33,71,41,41,99,88,19,20,18,17,95,75],[4,30,38,33,71,41,41,99,88,19,20,18,17,95,75],[23,30,38,33,71,41,41,99,88,19,20,18,17,95,75]*** Exception: euler18.hs:(16,1)-(17,72): Non-exhaustive patterns in function Main.extendpath

Answer 1

extendpath :: [[Integer]] -> [Integer] -> [[Integer]]
extendpath (xs:[]) (y1:y2:[]) = [y1:xs,y2:xs]
extendpath (xs:xss) (y1:y2:ys) = [y1:xs,y2:xs] ++ extendpath xss (y2:ys)

虽然它有效，但每次调用时路径数都会增加extendpath 一倍。但是行的长度仅增加 1。因此，一旦您有一个包含三行以上的三角形，在处理第四行（以及以后的每一行）时就会出现模式匹配失败。

在第二个（从零开始，因此包含三个元素的行）行之后，您有

--          LL   LR   RL   RR
extendpath [p_1, p_2, p_3, p_4] [v_1, v_2, v_3, v_4]
~> [v_1:p_1, v_2:p_1] ++ extendpath [p_2, p_3, p_4] [v_2, v_3, v_4]
~> [v_1:p_1, v_2:p_1] ++ [v_2:p_2, v_3:p_2] ++ extendpath [p_3, p_4] [v_3, v_4]
~> [v_1:p_1, v_2:p_1] ++ [v_2:p_2, v_3:p_2] ++ [v_3:p_3, v_4:p_3] ++ extendpath [p_4] [v_4]

最后一次调用没有匹配的模式。

现在，路径p_2和p_3结束在同一个地方，所以两者可以在下一行中扩展相同的两个值，但extendpath不考虑路径的结束位置。一般来说，n第-行有

n `choose` k

以第 -th 点结尾的路径k[这就是我在这里选择从零开始计数的原因]。扩展路径时，可能的扩展取决于路径的当前端点。

你需要一种不同的方法。尤其是第 67 题。

Answer 2

您有大量未涵盖的案例。这意味着您有部分功能，这是不好的。尽量避免它们。Maybe通常，使用类型构造函数很容易将它们转换为总函数。然后，您可以使用模式匹配来确保涵盖所有情况。另外，请注意head和tail是偏函数。

作为诊断此问题的技巧，我只需添加以下内容：

extendPath xs ys = error ("oops, pattern-match failed, arguments were: " ++ show xs ++ show ys)

确保那个案例在其他案例之后，因为它是一个包罗万象的。

您也必须为pathand执行此操作pathPyr。您可能希望通过打开警告来获得 Haskell 的帮助。

Answer 3

良好的错误警告级别将为您提供所需的所有信息。要触发它，请放入文件的头部：

{-# OPTIONS_GHC -Wall #-}

这很可能也会警告你一些其他的东西。哪个好。

Answer 4

-W当存在不完整的模式时，您可以通过将 GHC/GHCi作为参数提供给 GHC 或输入:set -WGHCi（并重新编译/重新加载您的文件！）来让 GHC/GHCi 向您发出警告。

Answer 5

捕捉缺失模式的另一种选择：

http://community.haskell.org/~ndm/catch/