F# - 限制函数输入中的区分联合大小写

Question

假设我正尝试在 F# 中构建一个简单的堆栈，如下所示：

type Stack =
| Empty
| Stack of String list

（我知道我可以递归定义它，但对于这个例子，假设我想在其中有一个列表）

然后我这样定义一个push操作：

let push item deck =
    match deck with
    | Empty -> Stack [item]
    | Stack d -> Stack (item::d)

但是当我进行 pop 操作时...我没有成功。我想做这样的事情：

let pop (Stack d) =
    match d with
    | h::[] -> h,Empty
    | h::t -> h,(Stack t)

现在，让我们也尝试忽略我可能想要 peek/pop 对操作而不是返回元组的事实。我想尝试的是编写一个 pop 操作，它只接受一个 Stack ，它首先不是空的。

换句话说，我只想让这个函数接受Discriminated Union的一种情况。但是，我立即收到警告：“此表达式的模式匹配不完整。例如，值 'Empty' 可能表示模式未涵盖的情况。

正如预期的那样（在警告之后），以下代码：

let empty = Empty
let s,st = pop empty

...编译并在运行时失败。我希望它在编译时失败。

我知道我可以为此使用其他选项，例如：

let pop stack =
    match stack with
    | Empty -> None, Empty
    | Stack (h::[]) -> Some h,Empty
    | Stack (h::t) -> Some h,(Stack t)

或：

let pop stack =
    match stack with
    | Empty -> Error "Empty Stack"
    | Stack (h::[]) -> Ok (h,Empty)
    | Stack (h::t) -> Ok (h,(Stack t))

（在这两种情况下，我可能根本不需要 Empty 情况...）

但我试图做一些更严格的限制。那么......我在这里错过了什么？有没有办法实现我的尝试？想要那个有什么意义吗？

Answer 1

问题出在您的模型上——有两种方法可以表示一个空堆栈：

let empty1 = Empty
let empty2 = Stack []

鉴于此，不清楚您希望它如何表现。这就是为什么我建议使用递归定义的堆栈，或者只使用列表。这是您的选择：

// type alias
type Stack<'a> = 'a list
// single-case DU
type Stack<'a> = Stack of 'a list
// traditional recursive type (which happens to be exactly equivalent to list<'a>)
type Stack<'a> = Empty | Stack of 'a * Stack<'a>

就是说，如果您真的只想保持现在的样子，并让它编译，您只需要匹配额外的 "empty"表示：

let pop stack =
    match stack with
    | Empty | Stack [] -> None, Empty
    | Stack (h::[]) -> Some h,Empty
    | Stack (h::t) -> Some h,(Stack t)

Answer 2

仔细考虑您要实现的目标。考虑以下函数：

let foo (s: Stack) = pop s

应该foo编译还是应该拒绝？想想看。

我假设你已经考虑过了，并给出了唯一合理的答案：你寻求的 "restriction" 现在应该也适用于 foo。也就是说，调用 foo 的人必须也只提供非空堆栈。

好的，很公平。但是让我们一路走到海龟：

let main argv = 
    printf "Provide directive: "

    let s = 
        match Console.ReadLine() with
        | "empty" -> Empty
        | _ -> Stack [1; 2; 3]

    let p = pop s

    0

现在这个程序应该编译还是被拒绝？显然，这取决于用户输入。 程序的类型取决于运行时值。这实际上是一个活跃的研究领域，它有一个名字：这样的程序叫做Dependently Typed。简而言之，当值（可能）携带类型时，但与 .NET RTTI 不同，编译器可以看到这些类型并可以证明它们之间的关系。令人着迷的东西。

无论好坏，F# 都不支持依赖类型，而且可能永远不会。

现在，我假设您可以接受没有依赖类型，而是希望您的 "restriction" 仅用于绝对 已知的情况 （在编译时）堆栈不为空。

如果是这种情况，那么将 DU 一分为二即可轻松解决您的问题：

type NonEmptyStack<'a> = NonEmptyStack of top: 'a * rest: 'a list
type Stack<'a> = Empty | NonEmpty of NonEmptyStack<'a>

let push item stack =
    match stack with
    | Empty -> NonEmptyStack (item, [])
    | NonEmpty (NonEmptyStack (top, rest)) -> NonEmptyStack (item, top::rest)

let pop (NonEmptyStack (top,rest)) = 
    match rest with
    | i::tail -> (top, Stack (NonEmptyStack (i, tail)))
    | _ -> (top, Empty)

注意 push 总是 returns 非空堆栈，而 pop 只接受非空堆栈。类型编码意义。这是他们应该做的。

F# - 限制函数输入中的区分联合大小写

F# - Restricting Discriminated Union case in function input

f#

discriminated-union