Блог

Я создаю настольную игру (типа) на F #, и у меня возникли небольшие проблемы с «функциональным» обходом массива.

У меня есть массив, который выглядит, например, как:

 val myArray : int [,] = [[1; 1; 0; 0; 0]
                         [0; 0; 1; 0; 0]
                         [2; 0; 0; 0; 3]
                         [0; 0; 0; 0; 0]
                         [0; 1; 0; 0; 1]]
  

Я хочу создать новый массив на основе приведенного выше, где:

1. Если элемент равен > 0, то в новом массиве должен быть номер 1
2. Если элемент равен = 0, то:
   1. Если элемент слева или справа или выше или ниже равен > 1, то в новом массиве число должно быть 2
   2. В противном случае, если элемент слева от right или выше или ниже равен = 1, то в новом массиве число должно быть 3
   3. В противном случае число должно быть 4

Это должно создать новый массив, который выглядит как:

 val myArray : int [,] = [[1; 1; 3; 4; 4]
                         [2; 3; 1; 3; 2]
                         [1; 2; 3; 2; 1]
                         [2; 3; 4; 4; 2]
                         [3; 1; 3; 3; 1]]
  

Я не вижу в F # никакого простого способа добиться этого. В C # я бы просто создал for цикл для этого, но я подумал, что может быть хитрый способ сделать это в F #, используя такие вещи, как map функции — mapi выглядел многообещающе, но, похоже, это дает доступ только к текущей рассматриваемой части и ее индексам, а не ко всему массиву…

Похоже, моя проблема заключается в том, что правила игры зависят от окружающей области, тогда как стандартные методы обхода, похоже, не предоставляют доступ к окружающей области — каков наилучший способ добиться того, что я делаю?

Я не думаю, что я использовал какой-либо хитрый трюк в этом решении. Я использовал Array2D.init для построения нового массива. Функция, требуемая init, определяет значение массива в каждой позиции.

Кроме того, я поместил сбор соседей в отдельную функцию. В функции neighbors я использовал понимание списка и выдачу только допустимых соседей, избегая проблем с углами и ребрами.

Это то, что я придумал (предупреждение: произойдет сбой, если 2D-массив равен 1×1 или пуст, я оставлю это читателю для защиты от этого случая):

 let neighbors r c (A:'a[,]) =
    [if r > 0 then yield A.[r-1,c]
     if r < Array2D.length1 A - 1 then yield A.[r 1,c]
     if c > 0 then yield A.[r,c-1]
     if c < Array2D.length2 A - 1 then yield A.[r,c 1]]

let newArray A =
    Array2D.init (Array2D.length1 A) (Array2D.length2 A) 
        (fun r c ->
            if A.[r,c] > 0 then 1 
            else
                match neighbors r c A |> List.max with
                | 1 -> 3
                | 0 -> 4
                | _ -> 2
        )
  

Тест в F # interactive:

 let myArray = array2D [[1; 1; 0; 0; 0]
                       [0; 0; 1; 0; 0]
                       [2; 0; 0; 0; 3]
                       [0; 0; 0; 0; 0]
                       [0; 1; 0; 0; 1]]

let result = newArray myArray
  

Результат:

 val result : int [,] = [[1; 1; 3; 4; 4]
                        [2; 3; 1; 3; 2]
                        [1; 2; 3; 2; 1]
                        [2; 3; 4; 4; 2]
                        [3; 1; 3; 3; 1]]
  

некоторые из моих мыслей:

Массив предназначен для доступа через индексацию. Если вы используете массив для хранения своих данных, то доступ к нему через индексацию является наиболее удобным способом.

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

 type NArray(A: int [,]) = 
    member x.Item with get (i,j) = (A.[i,j], i, j, A)
  

и вы также можете явно добавить четырех соседей к элементу:

 type NArray(A: int [,]) = 
    let get i j di dj = 
        let newI = i   di
        let newJ = j   dj
        if newI < 0 || newI > A.GetLength(0) then None
        elif newJ < 0 || newJ > A.GetLength(1) then None
        else Some (A.[newI, newJ])

    member x.Item with get (i,j) = (A.[i,j], get i j 0 1, get i j 0 -1, get i j 1 0, get i j -1, 0)
  

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

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