1

私は関数型プログラミングにまったく慣れていません。これは SML の宿題です。

整数のリストがあり、順序付けられたペアのリストを取得しようとしています。ペアの 2 番目のエントリは、最初のリストに最初のエントリが表示された回数です。

例えば：

[2,3,3,5] => [(2,1),(3,2),(5,1)]

私は誰かがこれを実装することを望んでいませんが、私が探している高階関数の種類、および/または正しい方向へのポインタを教えてください。繰り返しますが、関数型プログラミングはまったく新しいものであり、SML 言語はさらに新しいものです。

私の最初の考えは、 を使用したいというmapことでしたが、同様のアイテムを追跡またはマージする方法がわかりません。私は、各項目を 2 番目のエントリが 1 に等しい順序付けられたペアにすることしかできませんでした...まったく役に立ちません。

4

2 に答える 2

3

したがって、これにはおそらく のような折り畳みを使用する必要がありますfoldl。

一般に、使用するmapか折り畳むかを決定するとき (ここで折り畳みは、またはのいずれfoldlかを意味しますfoldr)、次の経験則を使用できます。

取得したいリストに取得したリストとまったく同じ数の要素がある場合は、おそらくmap. それ以外の場合は、折り目が必要になります。

理由は次のとおりです。リスト内の各要素に対してmap、変換された要素が出力に生成されます。一方、fold はより一般的で、やりたいことは何でもできます。(そして、実際にmap折り畳みを使用して実装することもできます。これは、もちろん、物事を不必要に複雑にする必要がないという意味ではありません)

完全を期すために、折り畳みがどのように機能するかについて簡単に説明しましょう。折り畳みはリスト (foldl左foldrから、右から、したがって名前) を実行し、アキュムレータで一度に 1 つの要素で結果を構築します。

例で見てみましょう：

foldl (fn (e, a) => e + a) 0 [5, 3, 7, 10]

e現在作業中の要素とaアキュムレータ変数 (つまり、現在の結果) は次のとおりです。を開始値としてa = 0指定0したため、 から開始します。

|  e | a  | new a
-------------------------
| 5  | 0  |  5 +  0 = 5
| 3  | 5  |  3 +  5 = 8
| 7  | 8  |  7 +  8 = 15
| 10 | 15 | 10 + 15 = 25
|    | 25 |

これにより の最終値aが得25られ、関数がリスト内の要素を合計したことがわかります。どの反復でも、 の値がaこれまでのリスト内の要素の合計であることに注意してください。また、各ステップでこのリストを拡張して 1 つ以上の要素を含める方法に注目してください。

これは、この問題を解決するために私が推奨する一種のアプローチです。

  • のベース値がaどうあるべきかを検討してください。(入力として取得した結果と同じ[]です。)
  • 次に、より小さなリストから結果を取得し、それを拡張して別の要素を含める方法を検討してください。
于 2013-06-28T19:40:35.137 に答える
0

折りたたみを使用する以外に、別のヒントがあります。[(2,1),(3,2),(5,1)]は最終結果であるため、fold が使用する累積関数の戻り値はこの型を持つ可能性があります。(int * int) list. 次に、問題を次のように減らしました。

foldl (fn (elem, acc) => ...) [] xs

どこに、たとえば、たとえば、にf挿入する必要があります。は、挿入関数と見なすことができます。または、同様に、次のようなものを生成する限り、そのような挿入関数を呼び出すことができます(つまり、既に見つかった要素を調べ、見つかった場合はそれを増やし、見つからない場合はカウント 1 で挿入します。elem5accum[(2,1),(3,2)]f[(2,1),(3,2),(5,1)]

于 2013-07-08T11:21:13.807 に答える