f# - 关于 F# 的堆栈和列表的问题

Question

堆栈与 F# 中的 List 相同吗？ F#中的堆栈和序列怎么样？队列呢？

Answer 1

堆栈和队列是抽象数据类型，可以通过多种不同方式实现。 F# 列表是作为不可变的单链表实现的。由于从单向链表的前面添加或删除项目是一个常数时间操作，F# 列表可以很好地表示堆栈。但是附加到列表是线性时间的，因此它们不太适合队列。

如果您需要一个临时堆栈，那么您不妨使用内置的 System.Collections.Generic.Stack<T> .对于持久堆栈，您可以自己实现。这个界面可能是一个好的开始:

type IStack<'A> =
    abstract member Push : 'A -> IStack<'A>
    abstract member Pop : unit -> 'A * IStack<'A>

或作为递归数据类型:

type Stack<'A> = Stack of 'A * Stack<'A> | Empty

但是尝试回答您的问题，尽管堆栈和 F# 列表不一样，但列表在函数式编程中无处不在，并且由于它们的性能特征，它们被用于 C# 程序员自然会接触到堆栈的地方。由于它们是持久的，因此它们也更适合函数式程序(转换不可变数据结构而不是修改可变数据结构)。