3

私は Haskell の初心者です。問題があります。「区切り」が表示されるすべての場所で、リストをリストのリストに分割する関数を作成する必要があります。

4

3 に答える 3

7

再帰を介してリストで機能する関数を開発する方法の理解を深める手助けをします。実際のコードでより一般的な「高レベル」の方法で何が起こっているかをよりよく理解できるように、最初に「低レベル」の方法でそれを行う方法を学ぶことが役立ちます。

まず、処理するデータの種類の性質について考える必要があります。リストは、ある意味で、Haskell で再帰的に定義された型の標準的な例です。リストは、空のリストであるか、を介してリストと結合された[]リスト要素です。この2つの可能性しかありません。空のリストは、その定義でそれ自体を参照していないため、基本ケースと呼びます。基本ケースがなければ、再帰は決して「底をつく」ことはなく、無期限に継続します!aa : list

リストの定義に 2 つのケースがあるという事実は、リストを操作する関数の定義で 2 つのケースを考慮する必要があることを意味します。Haskell で複数のケースを考慮する標準的な方法は、パターン マッチングです。Haskell 構文には、パターン マッチングを行う方法がいくつかありますが、ここでは基本的なcase式のみを使用します。

case xs of
  []    ->  ...
  x:xs' ->  ...

これらは、リストで考慮しなければならない 2 つのケースです。1 つ目は、リテラルの空のリスト コンストラクターに一致します。2 番目は、要素を追加するコンストラクターに一致し、:2 つの変数xと をxs'リストの最初の要素と残りの要素を含むサブリストにバインドします。

最初のケースに一致するリストが関数に渡された場合、最初のリストが空だったか、最後の要素をはるかに超えてリストの再帰を完了したことがわかります。いずれにせよ、処理するリストはもうありません。終了するか (呼び出しが末尾再帰の場合)、応答構築の基本要素を、これを呼び出した関数に (返すことによって) 戻す必要があります。あなたの答えがリストになる場合、基本要素は通常空のリストになり[]ます。

2 番目のケースに一致するリストが関数に渡された場合、空でないリストが渡されたことがわかります。さらに、有用な値にバインドされた新しい変数がいくつかあります。これらの変数に基づいて、次の 2 つのことを決定する必要があります。

  1. リストの残りの部分で正しい答えが得られると仮定して、その 1 つの要素でアルゴリズムの 1 つのステップを実行するにはどうすればよいでしょうか?
  2. その 1 つのステップの結果を、リストの残りのステップで実行した結果と組み合わせるにはどうすればよいですか?

これらの質問に対する答えを見つけたら、それらを組み合わせた式を作成する必要があります。リストの残りの部分の答えを得るには、リストの残りの部分で再帰呼び出しを呼び出すだけです。次に、最初の要素と結合の手順を実行する必要があります。

リストの長さを見つける簡単な例を次に示します

listLength :: [a] -> Int
listLength as =
  case as of
    []    -> 0                  -- The empty list has a length of 0
    a:as' -> 1 + listlength as' -- If not empty, the length is one more than the
                                -- length of the rest of the list

リストから一致する要素を削除する別の例を次に示します。

listFilter :: Int -> [Int] -> Int
listFilter x ns =
  case ns of
    []    -> []                            -- base element to build the answer on
    n:ns' -> if n == x
               then listFilter x ns'       -- don't include n in the result list
               else n : (listFilter x ns') -- include n in the result list

さて、あなたが尋ねた質問は、リストの基本的な再帰内のセパレーターを識別するための二次的な「リストマッチング」再帰を伴うため、もう少し難しいものです。問題のどこにいるかに関する追加情報を保持するために、再帰関数に追加のパラメーターを追加すると役立つ場合があります。2 つのパラメーターをタプルに入れることで、同時にパターン マッチを行うこともできます。

case (xs, ys) of
  ([]   , []   ) -> ...
  (x:xs', []   ) -> ...
  ([]   , y:ys') -> ...
  (x:xs', y:ys') -> ...

これらのヒントが、問題を解決するのに役立つことを願っています!

于 2013-08-25T22:43:08.150 に答える
3

明らかな方法で問題を軽減できるかどうか見てみましょう。

分割する xs と区切り文字として ys を指定して splitList が呼び出されたとします。xs が空の場合、問題は最も小さいので、その問題の答えは何ですか? 帰納的な解決策はこの決定に依存するため、ここで正しい答えを持つことが重要です。ただし、この決定は後で行うことができます。

OK、問題を軽減できるようにするために、リスト xs は空ではありません。したがって、少なくとも先頭要素 h と、リストの末尾にある小さな問題 t があります。xs@(h:t) と一致させることができます。より小さな問題の解決策を得るにはどうすればよいですか? さて、splitList は関数の定義によってその問題を解決できます。ここでの秘訣は、より小さな問題 zs=splitList t ys の解決策がわかっているときに、より大きな問題 (h:t) の解決策を構築する方法を理解することです。ここで、zs はリストのリスト [[a]] であり、t が最小の問題である可能性があるため、zs が最小の問題の解である可能性が高いことがわかります。したがって、zs で何をするにしても、それは最小の問題の解決にも有効でなければなりません。

  splitList [] ys = ... -- some constant is the solution to the smallest problem
  splitList xs@(h:t) ys = let zs = splitList t ys
                          in ... -- build a solution to (h:t) from solution to t
于 2013-08-26T08:32:49.373 に答える
1

テストする方法がわかりません。関数を .hs ファイルに書き込み、winGHCi を使用してこの関数を実行する方法を教えてくれる人はいますか?

WinGHCi は自動的に .hs ファイルと関連付けるので、ファイルをダブルクリックするだけで ghci が起動します。お気に入りのエディターを使用してファイルに変更を加えた後:r、ghci でコマンドを使用してファイルをリロードすることができます。

タイプミス、タイプエラーを修正し、正しいインデントを確認した後にプログラムをテストするには、定義した関数を異なる入力で呼び出してみてください (または QuickCheck を使用してください)。注記はまたはMaybeとして定義されます。を使用して抽出することができます(そして Nothing ケースのデフォルト値を提供します)。Just xNothingfromMaybex

また、パターン マッチングが網羅的であることを確認してください。

于 2013-08-26T21:53:07.870 に答える