F#中不可变的数据结构
提问于 2018-03-05 06:52:55
我试图在F#中使用它内置的泛型类型实现一个非常简单的堆栈。从命令式范式来看，有时很难想象如何避免易变性。
到目前为止，我使用push和pop运算符提供了一个简单的数据结构：
type Stack<'a> =
| Empty
| S of 'a list
with
member L.Push x =
match L with
| Empty | S ([]) -> S ([x])
| S (V) -> S (x :: V)
member L.Pop =
match L with
| Empty | S ([]) -> failwith "Error: Stack is empty"
| S (v::_) -> v
end我的想法是让Stack持有一个S of 'a list，在这里，我们用con ::操作符修改列表，使其不是对列表S进行变异，而是将其替换为S'。到目前为止，堆栈最多只能有一个元素，并且当将元素推到它时它不会增长--同样，当弹出时也不会收缩。
有人能给我一个提示，说明如何重写结构/以不同的方式思考它吗？
谢谢!
回答 2
Stack Overflow用户
发布于 2018-03-05 07:13:12
您可以通过简单地让一个列表充当堆栈，从而以一种更实用的方式来实现这一点。您可以将push和pop改为函数，而不是方法。
// Returns the new stack
let push item stack = item :: stack
// Returns (item, newStack) tuple or throws if stack is empty
let pop stack =
match stack with
| [] -> failwith "Stack is empty"
| item :: newStack -> item, newStack
// Example usage
let stack = []
let populatedStack = push "hello" stack
// populatedStack = ["hello"]
let item, emptiedStack = pop populatedStack
// item = "hello"
// emptiedStack = []Stack Overflow用户
发布于 2018-03-09 01:54:49
内置不可变列表已经是一个有效的堆栈结构。推送操作是::，使用模式匹配(如let (first,rest) = list )获得最后一项
如果你想从头开始创建一个堆栈。以下是一些实现。
1)
( a)堆栈不是空的
( b)或对前一个堆栈的值和引用。
type Stack<'a> =
| Empty
| Value of 'a * Stack<'a>
module Stack =
let isEmpty = function
| Empty -> true
| Value _ -> false
let empty = Empty
let push x stack = Value (x, stack)
let pop (Value (x, stack)) = x, stack
let stk =
Stack.empty
|> Stack.push 1
|> Stack.push 2
|> Stack.push 3
let rec loop stack =
if Stack.isEmpty stack
then ()
else
let first, rest = Stack.pop stack
printfn "First: %d" first
loop rest
loop stk您还可以选择一个记录作为底层数据结构。
type Stack<'a> = {
Value: 'a option
Next: Stack<'a> option
}这样，一个包含三个元素的堆栈看起来就像。
{Value=Some 3; Next=
{Value=Some 2; Next=
{Value=Some 1; Next=
{Value=None; Next=None}}}}您还可以选择一个带有value和next字段的类，并使用null作为最后一个元素。
重要的是如何处理这些结构。使用不可变数据结构的方法是使用递归函数而不是循环。
创建一个访问每个元素并在每个元素上执行函数的尾递归函数是fold函数，类似于一个forEach。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/49113155
复制相关文章
腾讯云开发者
