1

在Java中，很容易实现一种linkedlist风格stack。

我们只是创建了一个内部类Item，它有两个属性：value和next。

然后我们总是主要的第一项。

然后push，我们创建一个新的Item并让它的下一个指向当前，first item然后让当前first item成为新的item。

可以做类似的事情pop。

但是我怎样才能在 OCaml 中做到这一点？尤其是当我们想要in place modification( mutable) 时？

我说mutable是因为正常pop只弹出值，而不是新堆栈。

4

2 回答 2

5

OCaml 是一种多范式语言。使用可变数据一点也不难。但是学习没有它真的值得付出努力（恕我直言）。好处出奇的大，成本出奇的小。

尽管如此，这里是一个可变堆栈类型的快速草图。

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

为了补充 Jeffrey 的出色回答，我想指出，在这种情况下，很容易为 Stack 数据结构实现持久接口和可变接口，因为可变接口可以构建在持久接口之上。

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 回答