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 2倍になります。ただし、行の長さは1だけ増加します。したがって、3行を超える三角形があるとすぐに、4番目（およびそれ以降）の行を処理するときにパターン一致の失敗が発生します。

2番目の（ゼロベース、つまり3つの要素を持つ行）行の後に、次のようになります。

--          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は同じ場所で終了するため、次の行の同じ2つの値で2つを拡張できextendpathますが、パスがどこで終了するかは考慮されません。一般的に、n-番目の行には

n `choose` k

-番目のスポットで終わるパスk[ここでゼロベースのカウントを選択したのはそのためです]。パスを拡張する場合、可能な拡張はパスの現在のエンドポイントによって異なります。

別のアプローチが必要です。特に問題67の場合。

Answer 2

カバーされていないケースがたくさんあります。これは、部分的な関数があることを意味しますが、これは悪いことです。それらをできるだけ避けるようにしてください。Maybe多くの場合、型コンストラクターを使用してそれらを合計関数に変換するのは簡単です。次に、パターンマッチングを使用して、すべてのケースがカバーされていることを確認できます。headまた、とtailは部分関数であることに注意してください。

これを診断するためのハックとして、次のようなものを追加します。

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

それはキャッチオールなので、そのケースが他のケースの後に続くことを確認してください。

とについてもこれを行う必要がありpathますpathPyr。警告をオンにして、Haskellの助けを借りたいと思うかもしれません。

Answer 3

-WGHCに引数として指定するか、GHCiに入力する（およびファイルを再コンパイル/再ロードする）ことにより、不完全なパターンがある場合にGHC/GHCiに警告を表示させることができ:set -Wます。

Answer 4

適切なエラー警告レベルは、必要なすべての情報を提供します。それをトリガーするには、ファイルの先頭に置きます。

{-# OPTIONS_GHC -Wall #-}

これは、おそらく他の多くのものについても警告します。どっちがいい。

Answer 5

欠落しているパターンをキャッチする別のオプション：

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