F# - Return a value from for .. do

Question

I have a (random) set of numbers and I want to decide for any given number, whether the number is a composite one (meaning it can be created by two other numbers in the same given set).
Mathematical definition of my function:

Current code:

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

Issue:
I cannot return a boolean result from my iteration, when the element r has been 'found' as sum of the two elements s and t.

---

How could I solve the given problem as efficiently as possible?

If somebody finds an algorithm with a total run-time smaller than O(n²), then it is also fine by me.
[all called methods must also be faster than O(n²)]

Answer 1

You can't do what you're trying to do because F# is a language that uses expressions rather than statements. F# expressions always evaluate to a value (although that value might be unit: ()).

The code you originally posted doesn't compile because something of type unit is expected, that's because your if/then expression has no else branch. Consider the following:

let a = if x > 5 then 10

This code will produce a compiler error, that's obvious because we haven't specified what the integer value of a might be if x is not greater than 5.

Of course, this code will compile:

let a = if x > 5 then 10 else 5

If you provide and if without an else, the F# compiler will assume the type is unit so this is also valid code:

let a = if x > 5 then ()

This is because both cases still just return unit, there is no type mismatch.

Because F# uses expressions, everything has to be bindable to a value.

---

Anyway, you can solve this by using nested Seq.exists statements, this way you can check every combination of values.

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

I've changed some of your naming conventions (it's idiomatic for F# function parameters to be camelCased) and have made your function inline so it will work on any type that supports addition.

Answer 2

Generally, you don't want to use loops to implement complicated iterations / recursive functions in F#. That's what tail recursive functions are good for.

To get the computational complexity below O(n²), how about this: consider the set of candidate summands, which is the complete set of numbers at first. Now look at the sum of the largest and smallest number in this set. If this sum is larger than the target number, the largest number won't sum to the target number with anything. The same goes the other way around.

Keep dropping the smallest or largest number from the set of candidates until either the set is empty or a match has been found.

The code could look like this:

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"

When I look at the mathematical definition, it doesn't seem to be a requirement that the target number is in the set. But if this matters, just check beforehand:

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

Tom make this generic over the comparable type, the function could be marked inline.

Set operations are O(log n), we go over the whole thing once, multiplying O(n), making the total complexity O(n log n) (where n is the number of elements in the set).

---

Effective speed version

If it's about actual speed rather than "just" the computational complexity, arrays are probably faster than immutable sets. Here's a version that uses array indices:

/// 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)

Note that we could pre-sort the array if the same set is used repeatedly, bringing down the complexity for each call on the same set down to O(n).