遍历 F# 二维数组

Question

我将要用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. 否则，如果左侧或右侧或上方或下方的某个项 = 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看起来很有前途，但它似乎只能访问当前正在考虑的部分及其索引，而不能访问整个数组...

我的问题似乎在于游戏规则取决于周围的区域，而标准遍历方法似乎无法访问周围的区域 - 有什么最好的方法来实现我所做的事情？

- David_001

Answer 1

我认为在这个解决方案中我没有使用任何诡计。我使用了Array2D.init来构建一个新的数组。init所要求的函数确定每个位置上的数组值。

此外，我将邻居聚集在一个单独的函数中。在邻居函数中，我使用了列表推导式，并仅产生有效的邻居，避免了在角落和边缘周围出现问题。

以下是我想到的代码（警告：当2D数组为1x1或为空时，它将失败，我将让读者防范这种情况）：

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#交互测试：

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]]

- cfern

---

这看起来正是我所需要的，而且看起来比我之前创建的更像F#...虽然我的解决方案相当相似，我创建了一个全零数组，然后有一个嵌套的for循环来迭代原始数组。我也没有使用那个列表推导式，所以想想看，我可能根本不太接近这个... - David_001

Answer 2

一些我的想法：

数组被设计为通过索引进行访问。如果您使用数组来存储数据，那么通过索引访问是最方便的方式。

你需要的是一个数据结构，其中一个元素知道它的邻居在哪里。这种数据结构不是简单的数组。您可以通过增加数组来设计这样的数据结构：

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)

同样的问题在你想让序列或列表知道它们的邻居时会出现。它们被设计成不知道。如果列表中的一个元素知道它的前一个节点，那么它就不是单链表了。

当你选择一个数据结构时，你继承了它的优点和缺点。对于数组来说，你可以快速定位元素，但元素本身没有位置概念。其他数据结构，如线索二叉树或双向链表，它们的元素知道它们所在的位置。但代价是需要更多的存储空间。

- Yin Zhu