Looping vs recursion with F #

Question

The sample code here solves the Euler project problem:

Starting from number 1 and moving clockwise to the right, the direction of the spiral 5 by 5 is formed as follows:

21 22 23 24 25 20 7 8 9 10 19 6 1 2 11 18 5 4 3 12 17 16 15 14 13 

You can verify that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals of 1001 per 1001 spiral formed in the same way?

but my question is a question of the style of functional programming, and not how to get the answer (I already have it). I try to talk a little about functional programming, avoiding the actual loops in my solutions, and therefore came up with the following recursive function to solve problem 28:

 let answer = let dimensions = 1001 let max_number = dimensions * dimensions let rec loop total increment increment_count current = if current > max_number then total else let new_inc, new_inc_count = if increment_count = 4 then increment + 2, 0 else increment, increment_count + 1 loop (total + current) new_inc new_inc_count (current + increment) loop 0 2 1 1 

However, it seems to me that my function is a bit messy. The following imperative version is shorter and clearer even after taking into account the fact that F # forces you to explicitly declare variables as mutable and does not include the + = operator:

 let answer = let dimensions = 1001 let mutable total = 1 let mutable increment = 2 let mutable current = 1 for spiral_layer_index in {1..(dimensions- 1) / 2} do for increment_index in {1..4} do current <- current + increment total <- total + current increment <- increment + 2 total 

Ignoring the fact that people with more maths ability solved the problem analytically, is there a better way to do this in a functional style? I also tried using Seq.unfold to create a sequence of values ​​and then pass the resulting sequence to Seq.sum, but this turned out to be even more messy than my recursive version.

Answer 1

Since you did not describe the problem you are trying to solve, this answer is based only on the F # code you posted. I agree that the functional version is a bit messy, but I think it can be clearer. I really don't understand the nested for loop in your imperative solution:

 for increment_index in {1..4} do current <- current + increment total <- total + current 

You are not using increment_index for anything, so you can just multiply increment and current by four and get the same result:

 total <- total + 4*current + 10*increment current <- current + 4*increment 

Then your imperative decision will be:

 let mutable total = 0 let mutable increment = 2 let mutable current = 1 for spiral_layer_index in {1..(dimensions- 1) / 2} do total <- total + 4*current + 10*increment current <- current + 4*increment increment <- increment + 2 total 

If you rewrite this to a recursive function, it becomes simple:

 let rec loop index (total, current, increment) = if index > (dimensions - 1) / 2 then total else loop (index + 1) ( total + 4*current + 10*increment, current + 4*increment, increment + 2 ) let total = loop 1 (0, 2, 1) 

The same could be written using Seq.fold like this (this is even more “functional” because in functional programming you use recursion only to implement basic functions like fold , which can then be reused):

 let total, _, _= {1 .. (dimensions - 1) / 2} |> Seq.fold (fun (total, current, increment) _ -> (total + 4*current + 10*increment, current + 4 * increment, increment + 2)) (0, 1, 2) 

NOTE. I am not sure if this really implements what you want. This is simply simplifying your imperative solution, and then rewrite it with a recursive function ...

Answer 2

Actually this is Project Euler Problem 28 and my F # solution around November 21, 2011 is very similar to the one suggested in Thomas's answer:

 let problem028 () = [1..500] |> List.fold (fun (accum, last) n -> (accum + 4*last + 20*n, last + 8*n)) (1,1) |> fst 

In fact, the solution to the original problem takes only a single-line simple fold along the list of all involved squares with angles in the diagonal nodes, penetrating the accumulated sum and value of the current diagonal element. Folding is one of the main idioms of functional programming; there is an excellent classic article A textbook on the versatility and expressiveness of folds that covers many important aspects of this basic template.