2

我stack正在OCaml使用array.

我希望它接受任何类型。这是我实施的一部分，我的问题也是关于它的。

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

因此，在上面，当我定义堆栈的类型时，就可以了。storageis a which is a array接受'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

您的storage字段是可变的，因此您可以在不同的时间将不同的数组放在那里。所以你可以用一个完全多态的空数组进行初始化（就像一个空列表）。

另一种方法是对storage字段使用选项类型并在第一次推送操作时创建数组。

我有时会在我的生产代码中遇到此类问题。我通常最终使用选项类型。

（更好的方法是对堆栈使用列表。除非您需要访问除顶部以外的元素，否则数组只会造成麻烦而不会带来任何好处。）

更新

这是一个函数，它返回一个两倍于所提供数组的数组。为了灵活性，不保证额外元素具有任何特定值（尽管实际上它们只是原始数组的第 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 回答
1

You could allocate the array lazily:

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

Your push function would then check whether the stack is initialised already and create the array of not.

However, on a more general note, I think you're better of defining your stack with an 'a list ref. Or even better, use an immutable stack, i.e. a list.

于 2013-02-21T17:18:36.947 回答