F# - Return 来自 for .. do 的值

Question

我有一组（随机）数字，我想为任何给定数字确定该数字是否为复合数字（意味着它可以由同一组中的其他两个数字创建）。
我的函数的数学定义：

当前代码：

let task1 (M : seq<'T>, r : 'T) : bool =
    if not(Seq.exists((=) r) M) then
        failwith "nope!"
    else
        for s in M do
            for t in M do
                if s + t = r then
                    true         // error
        false

问题：
当元素 r 是 'found' 作为两个元素 s 和 t 的总和时，我不能 return 我的迭代的布尔结果。

我怎样才能尽可能有效地解决给定的问题？

如果有人发现一个算法的总数运行-time小于O(n²)，那么我也可以。
[所有被调用的方法也必须比 O(n²) 更快]

Answer 1

你不能做你想做的事，因为 F# 是一种使用表达式而不是语句的语言。 F# 表达式的计算结果始终为一个值（尽管该值可能是单位：()）。

您最初发布的代码无法编译，因为需要 unit 类型的东西，那是因为您的 if/then 表达式没有 else 分支。考虑以下因素：

let a = if x > 5 then 10

此代码会产生编译器错误，这是显而易见的，因为我们没有指定如果 x 不大于 5 时 a 的整数值可能是多少。

当然，这段代码会编译：

let a = if x > 5 then 10 else 5

如果您提供 if 而没有 else，F# 编译器将假定类型为单元，因此这也是有效代码：

let a = if x > 5 then ()

这是因为两种情况都只是 return unit，没有类型不匹配。

因为 F# 使用表达式，所有内容都必须可绑定到一个值。

无论如何，你可以通过使用嵌套的 Seq.exists 语句来解决这个问题，这样你就可以检查每个值的组合。

let inline task1 items r =
    items |> Seq.exists (fun s ->
        items |> Seq.exists(fun t -> s + t = r))

我更改了您的一些命名约定（F# 函数参数惯用的驼峰式命名）并使您的函数 inline 因此它适用于任何支持加法的类型。

Answer 2

通常，您不想在 F# 中使用循环来实现复杂的迭代/递归函数。这就是尾递归函数的好处。

为了得到低于O(n²)的计算复杂度，这个怎么样：考虑候选被加数的集合，它首先是完整的数字集合。现在看看这个集合中最大和最小数字的总和。如果此总和大于目标数，则最大数将不会与目标数相加。反过来也是一样。

不断从候选集中删除最小或最大的数字，直到该集合为空或找到匹配项。

代码可能如下所示：

let rec f M x =
    if Set.isEmpty M then false else
    let biggest, smallest = Set.maxElement M, Set.minElement M
    let sum = biggest + smallest
    if   sum > x then f (Set.remove biggest M)  x
    elif sum < x then f (Set.remove smallest M) x
    elif sum = x then true
    else failwith "Encountered failure to compare numbers / NaN"

当我查看数学定义时，似乎并不要求目标数字在集合中。但如果这很重要，请事先检查一下：

let fChecked M x =
    if Set.contains x M then f M x
    else invalidArg "x" "Target number is not contained in set."

Tom 将此泛型化为可比类型，函数可以标记为 inline。

集合操作是 O(log n)，我们遍历一次，乘以 O(n)，使得总复杂度为 O(n log n)（其中n 是集合中元素的数量）。

有效速度版本

如果它是关于实际速度而不是 "just" 计算复杂性，数组可能比不可变集更快。这是一个使用数组索引的版本：

/// Version where M is types as an unsorted array we're allowed to sort
let f M x =
    Array.sortInPlace M
    let rec iter iLow iHigh =
        if iLow > iHigh then false else
        let sum = M.[iLow] + M.[iHigh]
        if   sum > x then iter iLow (iHigh - 1)
        elif sum < x then iter (iLow + 1) iHigh
        elif sum = x then true
        else failwith "Encountered failure to compare numbers / NaN"
    iter 0 (M.Length - 1)

请注意，如果重复使用同一组，我们可以对数组进行预排序，从而将同一组上的每次调用的复杂度降低到 O(n)。

F# - Return 来自 for .. do 的值

F# - Return a value from for .. do

iteration

big-o

f#

loops