list - 如何为 F# 中不能为空的列表定义数据结构？

Question

最近，我开始学习 F# 并且我正在努力处理有区别的联合、列表和结构。我找到了一个练习，我需要执行以下操作:

'定义一个 NonEmptyList<'a> 数据结构，它可以表示一个永远不能为空的列表'

试图

let NonEmptyList (input : List<'a>) = 
   match input with
   | [] -> failwith "List canot be empty"
   | [x] -> x

不确定这是否使用 let 关键字正确实现。即...我是否需要这种结构:

type NonEmptyList<'a> = struct
    | List

编辑 1

type NonEmptyList<'T> = 
  | Cons of 'T * List<'T>
  | Single of List<'T>

编辑 2

let list1 : NonEmptyList<'T> = Single[1..10]
let list2 : NonEmptyList<'T> = Cons([1..3],[1..3]) 

我收到一个解析器错误:此构造导致代码不如类型注释所指示的通用。类型变量 'T 已被约束为类型 'a list。

Answer 1

首先，我对任务的解读是给出一个类型定义(使用 type )而不是一个检查列表是否为空的函数。

要解决这个问题，最好先了解普通的 F# 列表:

type List<'T> = 
  | Cons of 'T * List<'T>
  | Empty 

这里，列表要么是空的(由 Empty 值表示)，要么包含一个 'T 类型的值，后跟另一个由 List<'T> 表示的列表。这样，您可以创建:

let nop = Empty                      // Empty list
let oneTwo = Cons(1, Cons(2, Empty)) // List containing 1 and 2 

因此，要回答这个问题，您将需要一个与 List<'T> 非常相似的定义，只是不能创建 Empty 列表。你可以从这样的事情开始:

type NonEmptyList<'T> = 
  | Cons of 'T * NonEmptyList<'T>

现在我删除了 Empty ，我们不能再创建空列表 - 但这并不能完全解决问题，因为现在你永远无法结束任何列表。我不会给出完整的答案以避免剧透，因为我认为弄清楚这一点是练习的重点，但是您需要以下内容:

type NonEmptyList<'T> = 
  | Cons of 'T * NonEmptyList<'T>
  | // One more case here

最后一种情况可能是什么，以便它不包含另一个 List<'T> (从而让我们结束一个列表)，但不是 Empty ，因此我们不能创建空列表？