functional-programming - 有没有办法将基于矩阵的图形表示转换为 OCaml 中的邻接列表之类的东西？

不幸的是，当你遇到一块节点时，循环遍历元素并运行 dfs 的典型算法很难在功能上实现。

相反，它们非常容易和自然地实施。让我们展示一下。LeetCode 的输入表示为：


grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]

直接映射到 OCaml 为

let grid = [
  ["1";"1";"1";"1";"0"];
  ["1";"1";"0";"1";"0"];
  ["1";"1";"0";"0";"0"];
  ["0";"0";"0";"0";"0"]
]

唯一的语法区别是您必须使用;而不是,作为分隔符。

OCaml 和一般的函数式语言中的迭代是使用迭代器来表达的。迭代器是一个高阶函数，它接受一个容器和另一个函数，并将这个函数应用于该容器的每个元素。因此，迭代不需要特殊的语言结构，比如foror while¹。

迭代器可以大致分为两组：文件夹和映射器。文件夹将函数应用于每个元素并累积结果。映射器创建一个新的数据结构，其中每个元素都是原始元素的映射（转换）。不映射每个元素的映射器，即产生可能小于输入的输出数据结构的映射器称为过滤器。最后，每个映射器都可以（并且通常是）使用文件夹实现，因此文件夹是最通用的迭代形式。

现在，当我们掌握了这些知识后，我们可以查看List以了解它提供了哪些迭代器。由于我们需要找到孤立岛屿的数量，因此输入表示不是最优的，我们需要将其转换为更合适的表示。从图论的角度来看，一个岛屿是一个连通的组件，我们需要将我们的土地划分为一组岛屿。显然，我们的输入数据结构不是很适合，因为它不允许我们有效地查询一个元素是否连接到其他元素。单链表中的所有查询都是线性的，因为它们必须从第一个元素到最后一个元素。所以我们需要找到一个更好的数据结构来表示我们关于世界地理的信息。

由于我们只is_land对有效表示感兴趣的是一组位置，其中每个位置表示为 x 和 y 坐标，

type pos = {x : int; y : int}

让我们为位置类型定义一个模块并在其中添加一些有用的功能，

module Pos = struct
  type t = pos
  let compare = compare   (* use structural compare *)
  let zero = {x=0; y=0}
  let north p = {p with y = p.y - 1}
  let south p = {p with y = p.y + 1}
  let east p = {p with x = p.x + 1}
  let west p = {p with x = p.x - 1}
end

最后，我们准备好将世界定义为一组位置，

module World = Set.Make(Pos)

现在我们可以遍历我们的矩阵并创建一个世界，

let is_land = function "1" -> true | _ -> false

let make_world input : World.t =
  snd @@
  List.fold_left (fun (pos,map) ->
      List.fold_left (fun ({x;y},map) piece ->
          if is_land piece
          then ({x=x+1; y}, World.add {x;y} map)
          else ({x=x+1; y}, map))
        ({x=1; y = pos.y + 1},map))
    ({Pos.zero with x = 1},World.empty)
    input

看看我们如何使用 List 迭代器对矩阵执行迭代。

接下来，我们将实现联合查找算法将一个世界划分为一组岛屿。让我们自上而下开发它。union-find 算法将一组元素划分为一组不相交的集合（通俗地称为商集）。我们的初始集合是World.t所有土地位置的集合。对于每个位置，我们需要找到该位置所在的岛屿列表is_connected。我们现在需要精确定义什么is_connected意思。就我们世界的几何而言，如果该位置的一块土地属于一个岛屿，或者它的任何邻居属于，则该土地pos与岛屿相连，其中的，islandislandislandneighborspos

let neighbors pos = [
  Pos.north pos;
  Pos.south pos;
  Pos.east pos;
  Pos.west pos;
]

sois_connected是使用List.exists迭代器定义的，

let is_connected pos island =
  List.exists (fun x -> World.mem x island)
    (pos :: neighbors pos)

现在，我们可以编写一个函数，将岛屿商集划分为一块土地所属的岛屿集和不与该土地相连的岛屿集。List.partition使用迭代器很容易实现，

let find_islands pos =
  List.partition (is_connected pos)

如果一个元素属于几个孤岛，那么这意味着它是一个连接元素，一个链接，连接了几个在我们找到这个元素之前被认为是断开的孤岛。我们需要一个函数，它将一个岛的几个部分连接成一个岛。同样，我们可以使用List.fold_left它，

let union = List.fold_left World.union World.empty

现在，我们拥有了所有必要的构建元素来找到我们的主要算法，

let islands world =
  World.fold (fun pos islands ->
      let found,islands = find_islands pos islands in
      World.add pos (union found) :: islands)
    world []

让我们重申一下它的实现。对于我们世界的每一部分，我们将我们的初始岛屿集（从一个空集开始）划分为这块属于和不属于的岛屿。然后我们union找到找到的岛屿并将当前的一块添加到新形成的岛屿中，并将这个岛屿添加到岛屿集合中。

请注意，在函数式编程语言中实现 union-find 是多么简单！

岛屿的数量显然是我们划分的基数，例如，

let number_of_islands world = List.length (islands world)

最后，solve以指定形式接受输入并返回岛屿数量的函数定义为：

let solve input = number_of_islands (make_world input)

让我们玩一点，

# solve [
  ["1";"1";"1";"0";"0"];
  ["1";"1";"0";"1";"0"];
  ["1";"1";"0";"0";"0"];
  ["0";"0";"0";"0";"1"]
];;
          - : int = 3
# solve [
  ["1";"1";"1";"1";"0"];
  ["1";"1";"0";"1";"0"];
  ["1";"1";"0";"0";"0"];
  ["0";"0";"0";"0";"1"]
];;
          - : int = 2
# solve [
  ["1";"1";"1";"1";"0"];
  ["1";"1";"0";"1";"1"];
  ["1";"1";"0";"0";"1"];
  ["0";"0";"0";"0";"1"]
];;
          - : int = 1
#

看起来不错！但是，如果它从一开始就不起作用怎么办？我们需要调试它。在函数式编程中调试很容易，因为您可以独立调试每个小函数。但是为此，您需要能够打印您的数据，并且我们World.t是一种抽象数据类型，打印为<abstr>. 为了能够打印它，我们需要定义一些打印机，例如，

let pp_pos ppf {x; y} = Format.fprintf ppf "(%d,%d)" x y
let pp_comma ppf () = Format.fprintf ppf ", "
let pp_positions ppf world =
  Format.pp_print_list ~pp_sep:pp_comma pp_pos ppf
    (World.elements world)
let pp_world ppf world =
  Format.fprintf ppf "{%a}" pp_positions world

现在我们可以安装它（我假设你正在使用解释器运行这个程序ocaml）utop，现在我们可以看到我们的算法如何将我们的世界划分为岛屿，

# #install_printer pp_world;;

# islands @@ make_world [
  ["1";"1";"1";"0";"0"];
  ["1";"1";"0";"1";"0"];
  ["1";"1";"0";"0";"0"];
  ["0";"0";"0";"0";"1"]
];;
          - : World.t list =
[{(5,4)}; {(4,2)}; {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1)}]

^1）我们仍然在 OCaml 中使用它们，但很少使用。

functional-programming - 有没有办法将基于矩阵的图形表示转换为 OCaml 中的邻接列表之类的东西？

问题描述

解决方案

推荐阅读