0

在学习 OCaml 半年之后，我仍然在functional programming和imperative programming位上苦苦挣扎。

它不是关于using list or array，而是关于 API 设计。

例如，如果我要为用户写作，我应该以何种方式stack呈现它functional ？imperative

stack应该有一个名为 的函数pop，这意味着将最后一个元素返回给用户并将其从堆栈中删除。因此，如果我设计我stack的functional方式，那么 for pop，我应该返回一个 tuple (last_element, new_stack)，对吗？但我认为它很丑。

同时，我觉得functional函数式编程的方式更自然。

那么，我应该如何处理这种设计问题呢？

编辑

我看到了stack的源代码，他们定义了这样的类型：

type 'a t = { mutable c : 'a list }

好的，标准库内部使用list的是不可变的，但将其封装在可变记录中。

我以这种方式理解这一点，对于用户来说，它始终是一个堆栈，因此不需要元组返回给客户端。

但是，它仍然不是一种功能性的方式，对吧？

4

2 回答 2

4

可变结构有时更有效，但它们不是持久的，这在各种情况下都很有用（主要用于回溯失败的计算）。如果不可变接口与可变接口相比没有或几乎没有性能开销，那么您绝对应该更喜欢不可变接口。

于 2013-07-10T11:20:40.397 回答
1

在功能上（即没有可变性），您可以List通过使用 head/tail 而不是 pop 来完全定义它，或者您可以按照您的建议让 API 通过返回一个元组来处理状态更改。这类似于状态单子的构建方式。

因此，要么由父作用域负责处理堆栈的状态（例如，通过递归），在这种情况下堆栈与列表完全一样，要么通过元组将部分责任加载到 API。

这是一个快速尝试（假装知道 O'Caml 语法）：

module Stack =
  struct
    type 'a stack = 'a list
    let empty _ = ((), [])
    let push x stack = ((), x::stack)
    let pop (x::stack) = (x, stack)
      | pop _ = raise EmptyStack
  end

一个用例是：

let (_, st) = Stack.empty ()
let (_, st) = Stack.push 1 Stack.empty
let (_, st) = Stack.push 2 st
let (_, st) = Stack.push 3 st
let (x, st) = Stack.pop st

除了显式处理元组之外，您可能希望st始终隐藏传递并发明一个使以下语法成为可能的运算符：

let (x, st) = (Stack.empty >>= Stack.push 1 >>=
               Stack.push 2 >>= Stack.push 3 >>= Stack.pop) []

如果你能做这个操作符，你就重新发明了状态单子。:)

（因为上面的所有函数都将状态作为它的柯里化最后一个参数，所以它们可以部分应用。为了对此进行扩展，所以发生的事情更明显，但可读性较差，请参见下面的重写。）

let (x, st) = (fun st -> Stack.empty st >>= fun st -> Stack.push 1 st
                                        >>= fun st -> Stack.push 2 st
                                        >>= fun st -> Stack.push 3 st
                                        >>= fun st -> Stack.pop) []

至少，这是处理状态和不可变数据结构的一种惯用方式。

于 2013-07-10T12:58:04.483 回答