パターンを使用してn番目の要素を検索する

Question

私はを使っています。Haskellの基礎を理解するために、Haskellを学んでください。私は関数型プログラミングとパターンマッチングの両方に非常に慣れていますが、後者の方がどのようにしてMathematicaを実行するかは非常に快適です。エラーException: ... Non-exhaustive patterns in function last1を与えたlast1 [1,2,3,4]を呼び出し、しかし

last1 :: [a] -> a 
last1 (_:x:[]) = x 

：4.1章でheadのナイーブな実装と同じ精神で

は、私がようlastのナイーブな実装を進めました。このエラーは、指定されたパターンがすべての可能な入力をカバーしていないことを意味し、通常はキャッチオールパターンが必要です（これは私が提供していません）。しかし、私はなぜ私が私の入力のためのエラーを得る正確にはわからない。

質問1：（私の間違ったアプローチの）私の理解では、最初の要素が_によって捕獲され、残りは私が意図していたまさにされていない、xに割り当てられますということです。しかし、私は[a] -> aを指定したので、これは型エラーを返すべきではありませんが、xがリストになりましたか？より良いの同じテーマに沿って：私は

last2 :: [a] -> a 
last2 [x] = x 
last2 (_:x) = last2 x 

質問2（他の可能性の中でも）としてそれを書くことができます知っている - これは作業last関数を記述する方法についてないであることを

注意Haskellのパターンマッチングを理解するには、パターンマッチングを使用して最後の要素を選択するか、より一般的には[1..10]のような指定されたリストからn番目の要素を選びますか？

This answerあなたはViewPatterns拡張子とのパターンマッチングを使用して最後の要素をバインドできることを示唆しているが、のような類似した「シンプル」のパターンはMathematicaのがでhead

のためにそこにないことを奇妙に思える、私は希望第六要素と

Range[10] /. {___, x_} :> x 
(* 10 *) 

を選び出すために

Range[10] /. {Repeated[_, {5}], x_, ___} :> x 
(* 6 *) 

：おそらくとしてそれを書きます

空でないリストの最後の要素を選択します。

これについては後で説明しますが、お詫び申し上げますが、それぞれのトピックとコンセプトに関連しています。違いが分かるように他の言語で処理される方法および類似点。

Answer 1

最初の試行の結果を理解するには、 リストデータがどのように定義されているかを確認する必要があります。リストはやや特殊な構文を楽しんでいますが、 のように書くとよいでしょう。

data List a = (:) a (List a) 
      | [] 

だから、あなたのリスト[1 .. 10]が実際に起因する（の右結合性に、また

(1 : (2 : (3 : (4 : [])))) 

として構成されている:)演算子は、last1のためのあなたのパターン は実際に見えますlike

last1 :: [a] -> a 
last1 (_:(x:[])) = x 

これは、「x」がリストの要素と同じ型の理由です。 （:)コンストラクタへの最初の 引数です。

パターンマッチングでは、リストのようなデータ構造を解体することができますが、 は、どのような "形状"が必要かを知る必要があります。そのため、直接 リストの最後の要素を抽出するパターンを指定することはできません。なぜなら、 はリストが持つことができる無限の長さなのでです。そのため、解決策（last2）は問題を解決するために再帰を使用します。あなたはどのパターンが長さ1のリストにあり、最後の要素がどこにあるかを知っています。すべて の場合は、最初の要素を破棄し、結果の短いリストの最後の要素 を抽出することができます。

パターンを追加することもできますが、 が役立つことは証明できません。あなたは

last2 :: [a] -> a 
last2 (x:[])  = x 
last2 (_:x:[]) = x 
last2 (_:_:x:[]) = x 
     ... 
last2 (x:xs) = last2 xs 

として、それを書くことができますしかし、例数が無限ずに、あなたが入力リストのすべての長さのための機能 を完了することができませんでした。 のリストが実際に無限に長くなるという事実を考慮すると、さらに疑わしいものになります。それに合わせるためにどんなパターンを使用しますか？

Answer 2

パターンマッチングを行う方法はありません。ビューパターンを使用せずに「最後」の要素を取得します。これは、リストの最後の要素を（少なくとも暗黙的に）再帰を使用せずに取得する方法がないためであり、さらに何が決定可能な最後の要素を取得する方法がありません。

あなたのコード

last1 (_:x:[]) = x 

は、私たちはあなたのコードが何をするか見るこの演習を完了した

last1 a = case a of 
       (_:b) -> case b of 
          (x:c) -> case c of 
              [] -> x 

に脱糖ことができ

last1 (_:(x:[])) = x 

ように解析する必要があります：あなたはリストに一致するパターンを書いたリストの最も外側のコンストラクタがコンスセルAである場合ND次のコンストラクタはコンスであり、3番目のコンストラクタはゼロです。

ので

last1 [1,2,3,4] 

の場合には、我々は

last1 [1,2,3,4] 
= last1 (1:(2:(3:(4:[])))) 
= case (1:(2:(3:(4:[])))) of 
     (_:b) -> case b of 
        (x:c) -> case c of 
            [] -> x 
= case (2:(3:(4:[]))) of 
     (x:c) -> case c of 
        [] -> x 
= let x = 2 in case (3:(4:[])) of 
        [] -> x 
= pattern match failure 

Answer 3

を持っているあなたの例

last1 (_:x:[]) = x 

は形だけa:b:[]の二つの要素、すなわちリストを含むリストと一致します。 _はバインドなしでリストの先頭と一致し、xは次の要素と一致し、空のリストはそれ自身と一致します。

パターンマッチングリストの場合、最も右側のアイテムだけがリストを表します。一致したリストの末尾です。

あなたのような機能をリストからn番目の要素を取得することができます：

getNth :: [a] -> Int -> a 
getNth [] _ = error "Out of range" 
getNth (h:t) 0 = h 
getNth (h:t) n = getNth t (n-1) 

このビルトイン例えば!!演算子を使用して[1..10] !! 5

Answer 4

あなたは確かに、リストの最後にパターンマッチングを行うためにViewPatternsを使用して、それでは、やらせることができます。

{-# LANGUAGE ViewPatterns #-} 

、我々のパターンマッチの前にリストを反転させることによって、あなたのlast1とlast2を再定義します。 これはO（n）になりますが、これはリストで避けられません。

last1 (reverse -> (x:_)) = x 

構文

mainFunction (viewFunction -> pattern) = resultExpression

は、あなたがそれを見ることができるので、

mainFunction x = case viewFunction x of pattern -> resultExpression

ための糖衣構文は、実際には、リストは、パターンがあることと一致する反転ですが、それはよりよい感じています。 viewFunctionは、好きな機能に過ぎません。 （延長の目的の一つは、彼らが がそれに関数を定義するときにそのデータ型の基本構造を使用する必要はありませんでしたので、人々はきれいにし、簡単にパターンマッチングのためのアクセサ関数 を使用できるようにすることでした。）

last1は、元のlastのように、リストが空の場合にエラーを返します。

*Main> last []
*** Exception: Prelude.last: empty list
*Main> last1 []
*** Exception: Patterns.so.lhs:7:6-33: Non-exhaustive patterns in function last1

まあ、OK、ではない正確に、私たちは

last1 _ = error "last1: empty list" 

を追加することで、あなたに

*Main> last1 []を与えることを変更することができます私たちは、もちろんlast2で同じトリックを使用することができます *** Exception: last1: empty list

：

last2 (reverse -> (_:x:_)) = x 
last2 _ = error "last2: list must have at least two elements" 

をしかし、あなたが例last4のためにこのように運ぶことができる

maybeLast2 (reverse -> (_:x:_)) = Just x 
maybeLast2 _ = Nothing 

を定義することがよりよいだろう。

last4 (reverse -> (_:_:_:x:_)) = x 

そして、reverseビューパターンを使用して、 (_:_:_:x:_)の意味を (ignore1st,ignore2nd,ignore3rd,get4th,ignoreTheRestOfTheList)から (ignoreLast,ignore2ndLast,ignore3rdLast,get4thLast,ignoreTheRestOfTheList)に変更しました。

Mathematicaでは、無視される要素の数を示すためにアンダースコアの数が使用されています。 Haskellで 、私たちはただ1 _を使用しますが、それはどの無視値に使用することができ、かつ 非対称リストコンストラクタ:の存在下で、意味はあなたがにしているどちら側に依存するので、a:bでaは 要素を意味し、bはリストでなければなりません。:は正しい結合 - a:b:cは a:(b:c)を意味するため、c:dである必要があります。これは、任意のリストパターンの最後のアンダースコアがignoreTheRestOfTheListを示し、reverseの存在が 存在することです。これは、リストの先頭の要素を無視することを意味します。

Mathematicaのフードの下に隠れている再帰/バックトラッキングは、ここではviewFunction reverse（これは再帰関数です）では明示的です。