找到非详尽的模式

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

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

你需要一个不同的方法.特别是问题67.