.net - 查找链表 F# 的总和

Question

如何使用 F# 中的函数找到链表元素的总和？

Answer 1

F# 有一个内置的“链表”（通用）类型 - 刚刚被调用list，并且已经有一个计算总和的函数：

let list1 = [2; 3; 5]
List.sum list1

可以使用递归函数编写对列表的任意操作：

let rec sum l = 
  match l with
    | [] -> 0
    | head::tail -> head + (sum tail)

但在大多数情况下，使用内置fold函数就足够了：

let sum l =
  List.fold (fun total element -> total + element) 0 l

另请注意，上面的“naïve”递归函数不是tail-recursive，因此在应用于很长的列表时会崩溃。尾递归实现将是这样的：

let sum l =
  let rec sumAcc acc l = 
    match l with
      | [] -> acc
      | head::tail -> sumAcc (acc+head) tail
  sumAcc 0 l

基本上就是fold这样。

（如果有人不知道 F# 登陆此页面，我将添加此答案 - 他/她可能会对 F# 中的列表支持产生错误的想法）

Answer 2

I tried your example, it doesn't work, so I did fix it.

type lists = Nil | Link of (int * (lists ref))

let list1 = Link(3, ref (Link (2, ref Nil)))
let list2 = Link(6, ref (Link (4, ref Nil)))
let list3 = Link(9, ref (Link (6, ref Nil)))

let rec sum = function      // or  let rec sum list = match list with
    | Nil              -> 0
    | Link(head, tail) -> head + sum !tail

You don't need to define Integer of int , if you do it, you'll have to tag all numbers with Integer

Answer 3

只是为了完整起见：

let sum l =
   l 
   |> List.reduce (+)

也会成功的。类型推断将推断 l 为 int 列表，因此如果您需要其他数字类型，您可以这样做（例如 long 列表）：

let sum (l:list<int64>) =
   l 
   |> List.reduce (+)

或这个：

   let inline sum l =
      l
      |> List.reduce (+)

内联将概括 sum 函数以适用于提供名为“+”的静态函数的任何类型。要使用它，您将拥有如下代码：

let mylist = [1;2;3;4]
let sumOfMyList = sum mylist;;

我还要说，根据我的经验，使用列表折叠和相关函数是比滚动自己的递归函数更好的方法。

Answer 4

let rec sum a = 
    match a with
    |Nil -> 0
    |Link(s,t) -> s+(sum (!t))