С ++ на F # плавный перевод

Question

Привет, ребята, у меня есть следующий фрагмент кода из 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);      
}

Я могу без проблем перевести его на F # напрямую.

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;

Конечно, это, вероятно, заставляет большинство из вас съеживаться, поскольку F # не предназначался для использования.Этот код имеет некоторые «некошерные» концепции для F #, такие как циклы do-while и изменяемые данные.

Но то, что мне было бы интересно увидеть, - это "правильный" перевод F # с неизменяемыми данными и своего рода эквивалентом выполнения.

Answer 1

В качестве первого шага вы можете посмотреть, как упростить цикл while внутри цикла for.Одним из вариантов является использование Seq.initInfinite для генерации последовательности, которая даст вам любое количество случайных координат X, Y.Затем вы можете использовать Seq.find, чтобы найти первое, которое относится к пустому полю доски.

Я также изменил isEmpty, чтобы взять кортеж (так что вы можете передать в качестве аргумента Seq.find с использованием частичногоприложение функции), и я изменил некоторые имена, чтобы следовать более стандартному стилю F # (вы обычно не использовали бы венгерскую нотацию имен):

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

Я думаю, что это довольно элегантное функциональное решение.Это может быть немного медленнее, чем императивное решение, но дело в том, что функциональный стиль облегчает написание и изменение реализации, как только вы ее изучите (вы всегда можете использовать императивный стиль в качестве оптимизации).

Чтобы избежатьвсе изменяемые состояния, вам нужно сначала создать места для препятствий, а затем инициализировать массив.Например, вы можете рекурсивно добавлять новые координаты к набору, пока он не наберет нужную длину.Затем вы можете сгенерировать массив, используя 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)

Это на самом деле не короче и будет немного медленнее, поэтому я остановлюсь на первом решении.Тем не менее, это хорошее упражнение, показывающее рекурсию и наборы ...

Answer 2

Вот моя попытка:

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)

Вы можете удалить Seq.filter, если доска пуста в начале.Как и в решении Томаса, он генерирует бесконечную последовательность позиций.Затем он удаляет плохие и дублированные позиции.Наконец, он обновляет доску первыми элементами nObstacles.