Как преобразовать алгоритм в функциональное программирование? - PullRequest
Новая
       6

Как преобразовать алгоритм в функциональное программирование?

0 голосов
/ 22 января 2019

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

Рассмотрим следующий простой алгоритм, который я написал на python. Получает список уровней дерева. Каждый уровень представляет собой список узлов, где узел содержит идентификатор, (изначально) пустой список детей и указатель на его родительский узел. Это упорядочивает дерево так, что у каждого родителя есть его дети в его списке детей, и возвращает корень (и). Например, следующий вход: 

[[{"id": 10,
    "children": [],
    "parent_id": null}],
  [{"id": 12,
    "children": [],
    "parent_id": 10},
   {"id": 18,
    "children": [],
    "parent_id": 10},
   {"id": 13,
    "children": [],
    "parent_id": 10}],
  [{"id": 17,
    "children": [],
    "parent_id": 12},
   {"id": 16,
    "children": [],
    "parent_id": 13},
   {"id": 15,
    "children": [],
    "parent_id": 12}]}]

Будет преобразовано в следующий вывод: 

[{"id": 10,
  "children":
   [{"id": 12,
     "children":
      [{"id": 17,
        "children": [],
        "parent_id": 12},
       {"id": 15,
        "children": [],
        "parent_id": 12}],
     "parent_id": 10},
    {"id": 18,
     "children": [],
     "parent_id": 10},
    {"id": 13,
     "children":
      [{"id": 16,
        "children": [],
        "parent_id": 13}],
     "parent_id": 10}],
  "parent_id": null}]

Код: 

def build_tree(levels):
            ids_to_nodes = []
            for i in range(len(levels)):
                    level = levels[i]
                    ids_to_nodes.append({})
                    for node in level:
                            ids_to_nodes[i][node["id"]] = node

                    if i > 0:
                            for node in level:
                                    levels[i - 1][node["parent_id"]]["children"].append(node)

            return levels[0].values()

Самое близкое, что мне удалось реализовать в эликсире, это 

def fix_level(levels, ids_to_nodes, i) do
      if i < length(levels) do
              level = Enum.at(levels, i)
              new_level =
              Enum.reduce level, %{},  fn node, acc ->
                Map.put(acc, node["id"], node)
              end
              ids_to_nodes = ids_to_nodes ++ [new_level]

              if i > 0 do
                Enum.reduce level, Enum.at(ids_to_nodes, i - 1)[node["parent_id"]], fn node, acc ->
                  Map.put(acc, "children", Enum.at(ids_to_nodes, i - 1)[node["parent_id"]]["children"] ++ [node]) # Doesn't work coz creates new map
                end
              end

              fix_level(params, ids_to_nodes, i + 1)
      end
      Map.values(ids_to_nodes[0])
    end


  def fix(levels) do
    fix_level(levels, ids_to_nodes, 0)
  end

Я знаю, что код очень неэффективен во многих местах, особенно вокруг концов списков, - но я не уверен, как эффективно переписать их, и, что более важно, я полностью заблокирован в отмеченная линия. Я думаю, что слишком много думаю об императиве / объектно-ориентированном подходе. Помощь в понимании функционального программирования будет оценена.

1 Ответ

0 голосов
/ 22 января 2019

Попробуйте использовать рекурсию вместо циклов, начните с узлов, у которых нет parent_id (или nil), и рекурсивно создайте поддеревья для каждого из их дочерних элементов.

Приведенный ниже код упрощен, но в основном не требует пояснений.

Он получает дочерние элементы текущего parent_id (который равен nil для корневых узлов) и создает поддеревья для каждого из его дочерних узлов.

% {карта | key1: val1, key2: val2} - сокращение от Elixir для обновления карт 

defmodule TestModule do
    def build_tree(levels, parent_id \\ nil) do
        levels
        |> Enum.filter(& &1.parent_id == parent_id) # get children of parent_id
        |> Enum.map(fn level ->
            %{level | children: build_tree(levels, level.id)} # recursively build subtrees of current level
        end)
        # we should now have child nodes of parent_id with their children populated
    end
end

# sample input
levels = [
    %{id: 1, parent_id: nil, children: []},
    %{id: 2, parent_id: 1, children: []},
    %{id: 3, parent_id: 2, children: []},
    %{id: 4, parent_id: 2, children: []},
    %{id: 5, parent_id: 4, children: []},
    %{id: 6, parent_id: 1, children: []},
    %{id: 7, parent_id: 6, children: []},
    %{id: 8, parent_id: 6, children: []},
    %{id: 9, parent_id: nil, children: []},
    %{id: 10, parent_id: 9, children: []},
]

TestModule.build_tree(levels)
...