4

ハーバード CS 51 プログラミング コースのプログラミング課題を ocaml で解決しています。問題は、文字のリストをペアのリストに圧縮できる関数を定義することです。各ペアには、リスト内の文字と文字自体の結果的な出現回数が含まれます。つまり、この関数をリスト ['a' ;'a';'a';'a';'a';'b';'b';'b';'c';'d';'d';'d';'d'] 私たち[(5,'a');(3,'b');(1,'c');(4,'d')] のリストを取得する必要があります。この問題を解決するために、補助関数 go を使用する関数を思いつきました。

let to_run_length (lst : char list) : (int*char) list =
  let rec go i s lst1 =
    match lst1 with
      | [] -> [(i,s)]
      | (x::xs) when s <> x ->  (i,s) :: go 0 x lst1
      | (x::xs) -> go (i + 1) s xs
        in match lst with
          | x :: xs -> go 0 x lst
          | [] -> []

私の質問は次のとおりです。補助関数 go を定義せずに、ネストされたパターン マッチングを使用して再帰関数 to_run_length を定義することは可能ですか。この場合、すでに渡された要素のカウンターの状態をどのように保存できますか?

4

2 に答える 2

6

あなたが実装した方法to_run_lengthは正しく、読みやすく、効率的です。それは良い解決策です。（ちょっとしたこと：後のインデントinが間違っています）

中間関数を回避したい場合は、代わりに再帰呼び出しからの戻りにある情報を使用する必要があります。これは、もう少し抽象的な方法で説明できます。

  • 空リストのランレングスエンコーディングは空リストです
  • リストのランレングスエンコーディングx::xsは、
    • のランレングスエンコーディングが でxs始まる場合x、...
    • そうでない場合は、(x,1) ::ランレングス エンコーディングxs

(詳細を確認できるように、意図的にソース コードを提供していませんが、残念ながら、このような比較的単純な関数で隠すことはあまりありません。)

考察の材料: 通常、この種の手法は、末尾再帰関数と非末尾再帰関数を検討するときに遭遇します (私が行ったことは、tail-rec 関数を非末尾再帰形式に変換することに似ています)。この特定のケースでは、元の関数は末尾再帰ではありませんでした。引数/結果の流れが再帰呼び出しのみを「ダウン」する場合、関数は末尾再帰です (より大きな結果を構築するためにそれらを再利用するのではなく、それらを返します)。私の関数では、引数/結果の流れは再帰呼び出しのみを「上」にします (呼び出しには最小限の情報しかなく、すべてのコード ロジックは結果を検査することによって行われます)。実装では、フローは「ダウン」(整数カウンター) と「アップ」(エンコードされた結果) の両方になります。

編集：元のポスターのリクエストに応じて、ここに私の解決策があります：

let rec run_length = function
  | [] -> []
  | x::xs ->
    match run_length xs with
      | (n,y)::ys when x = y -> (n+1,x)::ys
      | res -> (1,x)::res
于 2012-10-23T10:11:44.420 に答える
0

この関数を書くのは良い考えではないと思います。現在のソリューションは問題ありません。

それでもやりたい場合は、2 つの方法のいずれかを使用できます。

1) 関数の引数を変更せずに。補助関数で現在使用されているアキュムレータを含むいくつかのトップレベルの変更可能な値を定義できます。

2）関数に引数を追加して、データを保存できます。継続渡しスタイルをグーグルで検索すると、いくつかの例を見つけることができます。

ハッピーハッキング！

PS 現在のソリューションは問題なく、改善する必要がないことを強調したいと思います。

于 2012-10-23T10:15:03.230 に答える