对用户定义的数据类型中的元素求和

Question

在介绍了 f# 中的预定义数据类型（即列表）以及如何对列表或序列的元素求和后，我正在尝试学习如何使用用户定义的数据类型。假设我创建了一个数据类型，将其命名为 list1:

type list1 = 
    A
  | B of int * list1

其中：

A代表一个空列表
B 通过在另一个列表前面添加一个 int 来构建一个新列表

所以 1,2,3,4 将用 list1 值表示：

B(1, B(2, B(3, B(4, A))))

我从 wikibook 了解到，使用列表我可以通过以下方式对元素求和：

let List.sum [1; 2; 3; 4]

但是我该如何着手对用户定义的数据类型的元素求和呢？任何提示将不胜感激。

编辑：我可以利用匹配运算符：

let rec sumit (l: ilist) : int = 
  match l with
  | (B(x1, A)) -> x1
  | (B(x1, B(x2, A))) -> (x1+x2)

sumit (B(3, B(4, A)))

我得到：

val it : int = 7

如果我有超过 2 个整数，我怎样才能使它仍然对元素求和（即 (B(3, B(4, B(5, A)))）得到 12？

Answer 1

解决此类问题的一个很好的通用方法是以文字形式或伪代码形式写出您的算法，然后一旦您弄清楚了您的算法，就将其转换为 F#。在这种情况下，您想对列表求和，看起来像这样：

找出算法的第一步是仔细定义问题的规范。我想要一个算法来总结我的自定义列表类型。究竟是什么意思？或者，更具体地说，这对于我的自定义列表类型可以具有的两种不同类型的值（A 和 B）到底意味着什么？好吧，让我们一次看一个。如果一个列表是类型 A，那么它代表一个空列表，所以我需要决定一个空列表的总和应该是多少。空列表的总和最合理的值为 0，因此规则为 "I the list is of type A, then the sum is 0"。现在，如果列表是类型 B，那么该列表的总和意味着什么？那么，B 类型列表的总和就是它的 int 值加上子列表的总和。

所以现在我们对 list1 可以拥有的两种类型中的每一种都有一个 "sum" 规则。如果是 A，则总和为 0。如果是 B，则总和为（值 + 子列表的总和）。该规则几乎逐字翻译成 F# 代码！

let rec sum (lst : list1) =
    match lst with
    | A -> 0
    | B (value, sublist) -> value + sum sublist

关于此代码，我想说明几点。首先，您以前可能见过也可能没有见过的东西（因为您似乎是 F# 初学者）是 rec 关键字。在编写递归函数时这是必需的：由于 F# 解析器实现方式的内部细节，如果函数要调用自身，则必须在声明函数名称和参数时提前声明。其次，这不是编写 sum 函数的最佳方法，因为它实际上不是尾递归的，这意味着如果您尝试求和，它可能会抛出 WhosebugException真的，真的一长串。在您学习 F# 的这一点上，您也许还不应该为此担心，但最终您将学习一种有用的技术，用于将非尾递归函数转换为尾递归函数。它涉及添加一个额外的参数，通常称为 "accumulator"（有时简称为 acc），并且上述 sum 函数的正确尾递归版本看起来像这样：

let sum (lst : list1) =
    let rec tailRecursiveSum (acc : int) (lst : list1) =
        match lst with
        | A -> acc
        | B (value, sublist) -> tailRecursiveSum (acc + value) sublist
    tailRecursiveSum 0 lst

如果您已经能够理解这一点，那就太好了！如果你还没有到那个地步，把这个答案加入书签，一旦你研究了尾递归就回来看它，因为这种技术（使用内部函数将非尾递归函数转换为尾递归函数函数和累加器参数）是一个非常有价值的函数，在 F# 编程中有各种应用。

Answer 2

除了尾递归之外，泛型编程对于函数式学习者来说可能是一个重要的概念。如果它只能保存整数值，为什么还要麻烦创建自定义数据类型呢？

一个列表的所有元素的总和可以抽象为对列表的所有元素重复应用加法运算符和一个初始状态为初始状态的累加器。这可以概括为功能折叠：

type 'a list1 = A | B of 'a * 'a list1
let fold folder (state : 'State) list =
    let rec loop s = function
    | A -> s
    | B(x : 'T, xs) -> loop (folder s x) xs
    loop state list 
// val fold :
//   folder:('State -> 'T -> 'State) -> state:'State -> list:'T list1 -> 'State
B(1, B(2, B(3, B(4, A))))
|> fold (+) 0
// val it : int = 10

使 sum 函数泛型化需要一点黑魔法，称为静态解析类型参数。签名并不漂亮，它基本上告诉您它期望类型上的 (+) 运算符能够成功编译。

let inline sum xs = fold (+) Unchecked.defaultof<_> xs
// val inline sum :
//   xs: ^a list1 ->  ^b
//     when ( ^b or  ^a) : (static member ( + ) :  ^b *  ^a ->  ^b)
B(1, B(2, B(3, B(4, A))))
|> sum
// val it : int = 10

对用户定义的数据类型中的元素求和

summing elements from a user defined datatype

f#

functional-programming

f#-interactive