C++ to F# smooth translation

Question

Hey folks, I have the following piece of 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 translate it to F# directly with no problem.

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 x y
        board.[x,y]<-Obstacle;

Of course this probably makes most of you cringe, since this is not the way F# was meant to be used. This code has some "unkosher" concepts for F#, such as do-while loops and mutable data.

But what I would be interested in seeing is a "proper" F# translation with immutable data, and some sort of do-while equivalent.

Answer 1

Here is my try:

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

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

Answer 2

As a first step, you can take a look how to simplify the while loop 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 board field.

I also changed isEmpty to take a tuple (so that you can pass as argument to Seq.find using partial function application) and I changed some names to follow more standard F# style (you generally wouldn't use hungarian naming notation):

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 X Y 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 quite elegant functional solution. It may be a bit slower than the imperative solution, but the point is that functional style makes it easier to write & change the implementation once you learn it (You can always use imperative style as optimization).

To avoid all mutable state, you'll need to generate locations for obstacles first and then initialize the array. For example, you could recursively add new coordinates to a set until it has the required length. Then you can generate 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 x y -> 
  if obstacles.Contains(x, y) then Obstacle else Empty)

This isn't really shorter and it will be a bit slower, so I'd stick to the first solution. However, it is a nice exercise showing recursion and sets...