2

を使用して実装stackしています。OCamlarray

どんなタイプでも受け入れてほしいです。これが私の実装の一部であり、私の質問もそれについてです。

type 'a stack = {mutable storage : 'a array; mutable n : int};;
let create () = {storage = Array.make 2 0; n = -1};;

したがって、上記で、スタックのタイプを定義するときは問題ありません。配列でstorageあるa'a arrayは、任意のタイプを受け入れます。

しかし、create関数を実装すると、問題が発生しました。どうすれば初期化でき'a arrayますか？できませんよね？作成するときに初期値を指定する必要がありますよね？

では、ポリモーフィズムのある配列を使用してスタックを作成するにはどうすればよいですか？

4

3 に答える 3

2

OCamlの配列を使ってスタックを実装するのはなぜですか？それは意味がありません。これはC++やJavaではありません。不変のスタック：

 type 'a stack = Empty | Stack of 'a * 'a stack

 let pop = function
   | [] -> raise (Invalid_argument "empty stack")
   | x :: s -> x, s

 let push x s = x :: s

 let is_empty s = (s = Empty)

可変スタック：

type 'a stack = 'a list ref

let create () = ref []

let pop s =
  match !s with
    | [] -> raise (Invalid_argument "empty stack")
    | x :: xs -> s := xs ; x

let push x s = (s := x :: !s)

let is_empty s = (!s = [])

PSアレイがどういうわけか高速になると主張する前に、テストを実行する必要があります。

于 2013-02-22T16:52:42.210 に答える
1

配列を遅延的に割り当てることができます。

type 'a stack = {mutable storage : 'a array option; mutable n : int}
let create () = {storage = None; n = -1}

次に、プッシュ関数は、スタックがすでに初期化されているかどうかを確認し、そうでない配列を作成します。

ただし、より一般的な注意点として、スタックを'リスト参照で定義する方がよいと思います。またはさらに良いことに、不変のスタック、つまりリストを使用します。

于 2013-02-21T17:18:36.947 に答える
1

フィールドstorageは変更可能であるため、さまざまな時間にさまざまな配列を配置できます。したがって、完全に多態的な（空のリストのように）空の配列で初期化できます。

別のアプローチは、フィールドにオプションタイプを使用storageし、最初のプッシュ操作で配列を作成することです。

プロダクションコードでこの種の問題が発生することがあります。私は通常、オプション型を使用することになります。

（さらに良いアプローチは、スタックにリストを使用することです。最上位以外の要素にアクセスする必要がない限り、配列は問題を引き起こすだけで、何のメリットもありません。）

アップデート

これは、提供された配列の2倍の大きさの配列を返す関数です。柔軟性のために、追加の要素が特定の値を持つことは保証されていません（実際には、元の配列の0番目の要素のコピーにすぎません）。

let double array =
    let len = Array.length array in
    if len = 0 then array  (* 2 * 0 = 0 *)
    else
        Array.init
            (2 * len)
            (fun x -> if x < len then array.(x) else array.(0))
于 2013-02-21T17:20:18.477 に答える