1

で、のスタイルJavaを実装するのは簡単です。linkedliststack

内部クラスを作成するだけItemで、2つのプロパティがあります：valueとnext。

次に、常に最初のアイテムをメインにします。

次に、のときpush、新しいものを作成し、Itemその次のポイントを現在のポイントにしてから、現在のポイントをfirst item新しいfirst itemものにしitemます。

同様のことができますpop。

しかし、どうすればOCamlでこれを行うことができますか？特に欲しいときin place modification（mutable）？

mutable通常popは値をポップアウトするだけで、新しいスタックではポップアウトしないためです。

4

2 に答える 2

5

OCamlはマルチパラダイム言語です。可変データを使用することはまったく難しくありません。しかし、それなしで行うことを学ぶことは本当に価値があります（IMHO）。メリットは驚くほど大きく、コストは驚くほど小さいです。

とはいえ、これは可変スタックタイプの簡単なスケッチです。

type 'a stack = { mutable stack: 'a list }

let new_stack () = { stack = [] }

let is_empty stack = stack.stack = []

let push x stack = stack.stack <- x :: stack.stack

let pop stack =
    match stack.stack with
    | [] -> raise Not_found
    | x :: xs -> stack.stack <- xs; x

（を定義することから始めることもできますがtype 'a stack = 'a list ref、このバージョンは、独自の可変レコードフィールドを持つ方法を示しています。）

于 2013-02-20T23:39:20.327 に答える
3

ジェフリーの優れた答えを補足するために、この場合、可変インターフェースは永続インターフェースの上に構築できるため、スタックデータ構造に永続インターフェースと可変インターフェースの両方を簡単に実装できることに注意してください。

module Impl = struct
  type 'a t = 'a list
  let empty = []
  let is_empty = function [] -> true | _ -> false
  let push x stack = x::stack

  let pop = function
    | [] -> raise Not_found
    | x::xs -> (x,xs)
end

module PersistentStack : sig
  type +'a t
  val empty : 'a t
  val is_empty : 'a t -> bool
  val push : 'a -> 'a t -> 'a t
  val pop : 'a t -> 'a * 'a t
end = struct
  include Impl
end

module MutableStack : sig
  type 'a t
  val new_stack : unit -> 'a t
  val is_empty : 'a t -> bool
  val push : 'a -> 'a t -> unit
  val pop : 'a t -> 'a
end = struct
  type 'a t = 'a Impl.t ref
  let new_stack () = ref Impl.empty
  let is_empty stack = Impl.is_empty !stack
  let push x stack = (stack := Impl.push x !stack)
  let pop stack =
    let (x, xs) = Impl.pop !stack in
    stack := xs;
    x
end
于 2013-02-21T09:40:44.067 に答える