4

ocaml で文字列を逆にするこの関数がありますが、型が間違っていると表示されます。なぜ、または何ができるのかわかりません:(

デバッグに関するヒントも大歓迎です!

  28 let reverse s =
  29   let rec helper i =
  30     if i >= String.length s then "" else (helper (i+1))^(s.[i])
  31   in
  32     helper 0

エラー: この式は char 型ですが、string 型の式が必要でした

ありがとうございました

4

3 に答える 3

9

あなたの実装は、予想される (線形) 時間と空間の複雑さを持っていません: 時間と空間の両方で 2 次であるため、要求された機能の正しい実装とは言えません。

文字列連結sa^sbは size の新しい文字列を割り当てlength sa + length sb、2 つの文字列で埋めます。これは、その時間と空間の両方の複雑さが長さの合計で線形であることを意味します。この操作を文字ごとに 1 回繰り返すと、2 次複雑度のアルゴリズムが得られます (割り当てられたメモリの合計サイズとコピーの合計数は になります1+2+3+....+n)。

このアルゴリズムを正しく実装するには、次のいずれかを実行できます。

  • 予想されるサイズの文字列を割り当て、入力文字列の内容を逆にしてその場で変更します

  • string list反転したサイズ 1 の文字列を作成String.concatし、一度にすべてを連結するために使用します (これにより、結果が割り当てられ、文字列が 1 回だけコピーされます)。

  • 二次的な動作を示さずに文字または文字列を繰り返し蓄積することを目的としたBufferモジュールを使用します (これは、償却された定数時間を追加する動的サイズ変更ポリシーを使用します)

最初のアプローチは最も単純で最速ですが、他の 2 つの方法は、文字列を連結するより複雑なアプリケーションでより興味深いものになりますが、最終結果がどうなるかを 1 つのステップで知るのは簡単ではありません。

于 2013-05-09T07:09:35.947 に答える
1

そのためにサードパーティのライブラリを使用することもできます。http://batteries.forge.ocamlcore.org/はすでに文字列を逆にする機能を実装しています

于 2013-05-16T10:48:03.810 に答える