Elixir 中的二叉树迷宫生成

Question

我在 Ruby 中以纯面向对象的方式实现了二叉树迷宫生成。我正在尝试在 Elixir 中重写它作为学习练习，但我运行遇到了 OO 与 FP 范式的一些问题。

我渲染了一个包含单元格的网格。当使用二叉树算法遍历网格时，对于每个单元格，我决定 link 向上与它旁边的北部或东部单元格。 linking，在 Ruby 实现中是双向的：

def link(cell, bidirectional=true)
  @links[cell] = true
  cell.link(self, false) if bidirectional
  self
end

def unlink(cell, bidirectional=true)
  @links.delete cell
  cell.unlink(self, false) if bidirectional
  self
end

所以它link是小区到邻居，邻居到小区。我无法弄清楚如何在 Elixir 中执行此操作。我有函数的第一部分：

def link(cell, neighbour, bidirectional) do
  %{ cell | links: cell.links ++ [neighbour]}
end



test "it links cells in a bidirectional way" do
  cell = Cell.create(1, 1)
  neighbour = Cell.create(2, 2)

  %{ row: _, column: _, links: cell_links } = Cell.link(cell, neighbour, true)
  assert Enum.member? cell_links, neighbour
  # ?? check if neighbour links includes cell, but cannot get a reference to "new" neighbour
end

但是双向调用给我带来了麻烦。我可以毫无问题地进行调用，但由于我正在处理不可变数据，我将永远无法使用正确的 links 数组获得对 "new" 相邻单元格的引用。

对我来说，为每个单元实现一个 GenServer 似乎有点像反模式。肯定有一种方法可以以纯功能方式实现此行为；不过，我是 FP 的新手，希望得到一些帮助。

Answer 1

在将 OO 映射到顺序 Elixir（通常是函数式语言）时可以使用的模式上，您可以创建一个数据对象（不是 OO 对象）并将其作为第一个参数传递给您的函数。这样，您就可以在每次调用时转换该数据。

因此，您的 api 的形状将类似于 def link(maze, cell, bidirectional \ true)。使用以 {x,y} 元组作为键并以地图作为值的地图来表示迷宫，您可以访问单个单元格并更新它们。

下面是一些未经测试的代码作为示例。

def Maze do
  def new, do: %{cells: %{], links: %{}, start: {0,0}}}

  def link(maze, cell1, cell2, bidirectional \ true) do
    maze
    |> put_in([:links, cell2], true)
    |> link_bidirectional(cell1, bidirectional)
  end

  defp link_bidirectional(maze, _, _, false), do: maze
  defp link_bidirectional(maze, cell1, cell2, _) do
    link(maze, cell2, cell1, false)
  end
end

编辑：这是链接的功能性解决方案

defmodule Maze do
  def new do 
    %{cells: %{{0, 0} => Cell.create(0,0)}, tree: {{0, 0}, nil, nil}}
  end

  def new_cell(maze, row, column) do
    # ignoring the tree for now
    put_in(maze, [:cells, {row, column}], Cell.create(row, column))
  end

  def link(maze, cell1, cell2, bidirectional \ true)
  def link(maze, %{} = cell1, %{} = cell2, bidirectional) do
    maze
    |> update_in([:cells, cell1[:origin]], &(Cell.link(&1, cell2)))
    |> do_bidirectional(cell1, cell2, bidirectional, &link/4)
  end
  def link(maze, {_, _} = pt1, {_, _} = pt2, bidirectional) do
    link(maze, maze[:cells][pt1], maze[:cells][pt2], bidirectional)
  end

  def unlink(maze, %{} = cell1, %{} = cell2, bidirectional \ true) do
    maze
    |> update_in([:cells, cell1[:origin]], &(Cell.unlink(&1, cell2)))
    |> do_bidirectional(cell1, cell2, bidirectional, &unlink/4)
  end

  defp do_bidirectional(maze, _, _, false, _), do: maze
  defp do_bidirectional(maze, cell1, cell2, _, fun) do
    fun.(maze, cell2, cell1, false)
  end
end

defmodule Cell do
  def create(row,column), do: %{origin: {row, column}, links: %{}}
  def link(self, cell) do
    update_in(self, [:links, cell[:origin]], fn _ -> true end)
  end
  def unlink(self, cell) do
    update_in(self, [:links], &Map.delete(&1, cell[:origin]))
  end
end

iex(26)> Maze.new() |>
...(26)> Maze.new_cell(0,1) |>
...(26)> Maze.new_cell(1,0) |>
...(26)> Maze.link({0,0}, {0,1}) |>
...(26)> Maze.link({0,0}, {1,0})
%{cells: %{{0,
     0} => %{links: %{{0, 1} => true, {1, 0} => true}, origin: {0, 0}},
    {0, 1} => %{links: %{{0, 0} => true}, origin: {0, 1}},
    {1, 0} => %{links: %{{0, 0} => true}, origin: {1, 0}}},
  tree: {{0, 0}, nil, nil}}
iex(27)>

Elixir 中的二叉树迷宫生成

Binary tree maze generation in Elixir

ruby

functional-programming

immutability

elixir