C ++ to F # smooth translation

Question

Hi guys, I have the following code from C ++.

for (int i=0; i < nObstacles; i++) { int x,y; bool bAlreadyExists; do { x = rand() % nGridWidth; y = rand() % nGridHeight; } while (HasObstacle(x, y)); SetObstacle(x, y, true); } 

I can directly translate it to F # without any problems.

 let R = new System.Random() for i=0 to nObstacles do let mutable bGoodToGo = false; let mutable x =0; let mutable y = 0 while not bGoodToGo do x <-R.Next(nWidth) y <-R.Next(nHeight) bGoodToGo <- IsEmptyAt xy board.[x,y]<-Obstacle; 

Of course, this probably makes most of you cringe, since that doesn't mean you have to use F #. This code has some non-Kosher concepts for F #, such as do-while loops and mutable data.

But what I would be interested to see is the “correct” translation of F # with immutable data and some kind of do-while equivalent.

Answer 1

Here is my attempt:

 Seq.initInfinite (fun _ -> rnd.Next(width), rnd.Next(height)) |> Seq.filter (fun (x, y) -> IsEmptyAt xy) |> Seq.distinct |> Seq.take nObstacles |> Seq.iter (fun (x, y) -> board.[x,y] <- Obstacle) 

You can remove Seq.filter if the board is empty at the beginning. As in Thomas' solution, it generates an infinite sequence of positions. Then it removes bad and duplicate positions. Finally, he updates the board with the first elements of nObstacles.

Answer 2

As a first step, you can see how to simplify the while inside the for loop. One option is to use Seq.initInfinite to generate a sequence that will give you any number of random X, Y coordinates. Then you can use Seq.find to find the first one that refers to an empty field field.

I also changed isEmpty to take a tuple (so you can pass as an argument to Seq.find using a partial function application), and I changed some names to follow the more standard F # styles (usually you won’t use the Hungarian naming convention) :

 let isEmpty (x, y) = board.[x,y] = -1 let rnd = new System.Random() for i = 0 to obstacleCount do let x, y = // Generate infinite sequence of random XY coordinates Seq.initInfinite (fun _ -> rnd.Next(width), rnd.Next(height)) // Find first coordinate that refers to empty field |> Seq.find isEmpty // We still have mutation here board.[x,y] <- Obstacle 

I think this is a pretty elegant functional solution. This may be a little slower than an imperative solution, but the fact is that the functional style simplifies writing and changing the implementation after studying it (you can always use the imperative style as an optimization).

To avoid any volatile state, you must first create places for obstacles, and then initialize the array. For example, you can recursively add new coordinates to a set until it has the required length. Then you can generate the array using Array2D.init :

 let rec generateObstacles obstacles = if Set.count obstacles = obstacleCount then obstacles else // Try generating new coordinate and add it to the set // (if it is already included, this doesn't do anything) obstacles |> Set.add (rnd.Next(width), rnd.Next(height)) |> generateObstacles let obstacles = generateObstacles Set.empty Array2D.init width height (fun xy -> if obstacles.Contains(x, y) then Obstacle else Empty) 

This is not very shorter, and it will be a little slower, so I will stick to the first solution. However, this is a good exercise showing recursion and a lot ...