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

Question

最近,我开始学习F#,我正在努力与歧视的工会合作,列出结构.我找到了一个练习,我需要做以下事情:

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

尝试

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

不确定是否使用let-keyword正确实现了这一点.即..我是否需要这种结构:

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已被转换为类型'列表.

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,所以我们不能创建空列表？

Answer 2

一个非空列表由一个头部和一个可选的非空尾部组成。您可以将这种类型表示为单例联合：

type NEL<'a> = NEL of 'a * NEL<'a> option
let l = NEL(1, Some(NEL(2, None)))

或记录类型：

type NEL<'a> = {head : 'a; tail : NEL<'a> option}
let l = { head = 1; tail = Some({head = 2; tail = None})}