3
\$\begingroup\$

The proper title of this question should be "Summations and products, and factorials oh my!".


After getting quite a bit of useful feedback on this question from @mjolka, and a comment, I decided that there were many things to be improved.

These are the following things that I've added/changed:

  • A factorial function which uses the product function.
  • Support for getting the sum, and product of sequences with no elements.
  • Strongly typed anonymous function parameters.

Again, for those who don't know, a summation is defined as follows:

$$\sum_{n=a}^{b}f(n)$$

And a product is defined as follows:

$$\prod_{n=a}^{b}f(n)$$

I'd like to know the following things, which are more or less mostly the same as the ones in the last question:

  • Am I writing this in a proper functional way?
  • How can I reduce the repetitiveness in my code?
  • Is there a way to improve performance? It already runs pretty fast, at approximately \$0.025\$ seconds for inputs of \$10\$).
  • Anything else?

Here's the code:

let inline summation (f: (double -> double)) low high =
    match (low, high) with
    | (low, high) when low <> high ->
        { low .. high } 
        |> Seq.map f
        |> Seq.sum
    | (low, high) when low = high -> 0.0
    | _ -> -1.0

let inline product (f: (double -> double)) low high =
    match (low, high) with
    | (low, high) when low <> high ->
        { low .. high }
        |> Seq.map f
        |> Seq.fold Checked.op_Multiply 1.0
    | (low, high) when low = high -> 1.0
    | _ -> -1.0

let inline factorial n =
    product (fun x -> x) 1.0 n

Here's a few small tests to ensure that the code works:

[<EntryPoint>]
let main argv =
    System.Console.WriteLine(summation (fun x -> x) 1.0 10.0)
    System.Console.WriteLine(product (fun x -> x) 1.0 10.0)
    System.Console.WriteLine(factorial 10.0)
    0

And here's expected output of the above tests:

55
3628800
3628800
\$\endgroup\$
2
\$\begingroup\$

There are a few problems with this code.

If low = high then product f low high should be equal to f low. In this code, it is equal to 1.

Similarly, if low = high then summation f low high should be equal to f low. In this code, it is equal to 0.


The code posted in my previous answer already correctly deals with empty sequences:

> let inline summation f low high = Seq.map f { low .. high } |> Seq.sum ;;

val inline summation :
  f:( ^a ->  ^b) -> low: ^a -> high: ^a ->  ^b
    when  ^a : (static member get_One : ->  ^a) and
          ^a : (static member ( + ) :  ^a *  ^a ->  ^a) and  ^a : comparison and
          ^b : (static member ( + ) :  ^b *  ^b ->  ^b) and
          ^b : (static member get_Zero : ->  ^b)

> summation id 0 -10 ;;
val it : int = 0

> let inline product f low high = Seq.map f { low .. high } |> Seq.fold Checked.(*) LanguagePrimitives.GenericOne< _ > ;;

val inline product :
  f:( ^a ->  ^b) -> low: ^a -> high: ^a ->  ^c
    when  ^a : (static member get_One : ->  ^a) and
          ^a : (static member ( + ) :  ^a *  ^a ->  ^a) and  ^a : comparison and
         ( ^c or  ^b) : (static member ( * ) :  ^c *  ^b ->  ^c) and
          ^c : (static member get_One : ->  ^c)

> product id 0 -10 ;;
val it : int = 1

The third case of each function definition seems to be there just to get rid of the warning about incomplete pattern matches.

Since the second case of the match is incorrect, and the third case should never run, we can do away with the pattern matching.


There is no need to constrain the type of f. Doing so removes the benefits of declaring the functions inline.


Whenever you find yourself writing (fun x -> x) you can just replace it with id.

\$\endgroup\$
3
\$\begingroup\$

Some comments:

    |> Seq.map f
    |> Seq.sum

is just

Seq.sumBy f

Otherwise, if perf really matters I would avoid using Seq, and probably combine the map and fold in the product case.

Also, rather than

match (low, high) with
| (low, high) when low <> high ->
    { low .. high } 
    |> Seq.map f
    |> Seq.sum
| (low, high) when low = high -> 0.0

I would use an if to avoid the warning about incomplete pattern match so it would become

if low=high then 0.0
else   {low .. high} |> Seq.sumBy f
\$\endgroup\$
  • \$\begingroup\$ I'm embarrassed that I forgot about sumBy! \$\endgroup\$ – mjolka Oct 21 '15 at 3:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.