7

Haskellの基本を理解するために、Learn YouAHaskellを使用しています。私は関数型プログラミングとパターンマッチングの両方に非常に満足していますが、後者はMathematicaがそれを行う方法にもっと慣れています。

head4.1章のナイーブな実装と同じ精神で、私は次のようなナイーブな実装を進めましたlast。

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

ただし、呼び出しlast1 [1,2,3,4]でエラーが発生しましException: ... Non-exhaustive patterns in function last1た。このエラーは、指定されたパターンがすべての可能な入力をカバーしていないことを意味し、通常、キャッチオールパターンが必要であることを理解しています（これは提供していません）。ただし、入力に対してこのエラーが発生する理由は正確にはわかりません。

質問1:(私の間違ったアプローチの）私の理解は、最初の要素がによってキャプチャされ_、残りがに割り当てられるxということです。これは、私が意図したものとは正確には異なります。しかし、私が指定したので、これはタイプエラーを与えるべきではありません[a] -> aが、x現在はリストになっていますか？

これは動作する関数の書き方ではないことに注意してくださいlast—私はそれを（他の可能性の中でも）として書くことができることを知っています

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

質問2： Haskellでのパターンマッチングをよりよく理解するという同じテーマに沿って、パターンマッチングを使用して、最後の要素、より一般的にはn、特定のリストから3番目の要素を選択するにはどうすればよい[1..10]ですか？

この答えは、拡張子とのパターンマッチングを使用して最後の要素をバインドできることを示唆していますが、のViewPatternsような類似の「単純な」パターンがないのは奇妙に思えますhead

数学では、私はおそらくそれを次のように書くでしょう：

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

6番目の要素を選択して

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

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

これが本文の後半で取り上げられていることをお詫びしますが、それぞれのトピックと概念を、私が知っている他の言語でどのように処理されるかと関連付けて、相違点と類似点を理解できるようにしています。

4

4 に答える 4

8

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

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

したがって、リスト[1..10]は実際には次のように構成されています。

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

さらに、（:)演算子の適切な結合性により、last1のパターンは実際には次のようになります。

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

そのため、「x」はリストの要素と同じタイプです。これは（:)コンストラクターの最初の引数です。

パターンマッチングを使用すると、リストなどのデータ構造を分解できますが、そのために必要な「形状」を知る必要があります。これが、リストの長さが無限にあるため、リストの最後の要素を抽出するパターンを直接指定できない理由です。そのため、作業ソリューション（last2）は再帰を使用して問題を解決します。あなたは、長さのリストがどのようなパターンを持っているか、そして最後の要素をどこで見つけるかを知っています。それ以外の場合は、最初の要素を破棄して、結果の短いリストの最後の要素を抽出できます。

必要に応じて、パターンを追加することもできますが、それが役に立たないことはわかりません。あなたはそれを次のように書くことができます

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

しかし、無限の数のケースがなければ、すべての長さの入力リストに対して関数を完了することはできません。リストが実際には無限に長くなる可能性があるという事実を考えると、さらに疑わしいです。それに合わせるためにどのパターンを使用しますか？

于 2012-09-28T23:08:26.157 に答える
2

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

あなたのコード

last1 (_:x:[]) = x

次のように解析する必要があります

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

脱糖することができます

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

この演習を完了すると、コードの機能がわかります。リストの最も外側のコンストラクターがconsセルで、次のコンストラクターがconsで、3番目のコンストラクターがnilの場合、リストに一致するパターンを記述しました。

だから

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
于 2012-09-28T23:06:19.257 に答える
2

あなたの例

last1 (_:x:[]) = x

2つの要素を含むリスト、つまりフォームのリストにのみ一致します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

于 2012-09-28T23:07:15.240 に答える
2

ViewPatternsリストの最後でパターンマッチングを行うために実際に使用できるので、次のようにします。

{-# LANGUAGE ViewPatterns #-}

パターンマッチングの前にリストを逆にして、last1とを再定義します。last2これによりO（n）になりますが、リストでは避けられません。

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

構文

mainFunction (viewFunction -> pattern) = resultExpression

のシンタックスシュガーです

mainFunction x = case viewFunction x of pattern -> resultExpression

つまり、実際にはリストが逆になり、パターンがそれに一致することがわかりますが、より良い感じがします。 viewFunction好きな機能です。（拡張機能の目的の1つは、パターンマッチングにアクセサー関数をクリーンかつ簡単に使用できるようにすることでした。これにより、データ型の基になる構造を使用して関数を定義する必要がなくなりました。）

last1元のリストと同じように、リストが空の場合、これによりエラーが発生lastします。

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

そうですね、正確ではありませんが、追加することで変更できます

last1 _ = error "last1: empty list"

それはあなたに

*Main> last1 []
*** Exception: last1: empty list

もちろん、同じトリックを使用できますlast2：

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

しかし、定義する方が良いでしょう

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

あなたは例えば：でこの方法を続けることができますlast4：

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

reverseまた、 viewpatternを使用して、のセマンティクスを(_:_:_:x:_)から (ignore1st,ignore2nd,ignore3rd,get4th,ignoreTheRestOfTheList)に 変更したことがわかります(ignoreLast,ignore2ndLast,ignore3rdLast,get4thLast,ignoreTheRestOfTheList)。

Mathematicaでは、アンダースコアの数は無視される要素の数を示すために使用されていることに注意してください。Haskellでは、1つだけを使用します_が、無視された値に使用できます。非対称リストコンストラクターが存在する場合、セマンティクスはどちらの側にいるかによって異なります。したがって、では、は要素を意味し、リストである必要があります（それ自体が正しい連想であるためである可能性があります-意味します ）。これが、リストパターンの最後のアンダースコアが再表示される理由であり、viewfunctionが存在する場合、これはリストの前の要素を無視することを意味します。:a:babc:d:a:b:ca:(b:c)ignoreTheRestOfTheListreverse

Mathematicaの内部に隠されている再帰/バックトラッキングは、ここではviewFunction reverse（再帰関数）で明示されています。

于 2012-09-29T02:18:26.880 に答える