Creating a list of paths from a Keyword list

Learning Questions & Discussions Resources Chat/Questions
, ,
1

I am super stuck on trying to get a list of paths from a keyword list. Let me give you some examples:

# This keyword list..
[:a, :b]
# Should produce this:
[[:a], [:b]]

# This keyword list..
[:a, b: [:c, d: :e]]
# Should produce this:
[
  [:a],
  [:b, :c],
  [:b, :d, :e],
]

# This keyword list..
[:a, b: [:c, d: [:e]]]
# Should produce this:
[
  [:a],
  [:b, :c],
  [:b, :d, :e],
]

The closest I’ve come is the following:

defmodule Path do
  def reduce_over_path([{field, path}], acc, fun) do
    reduce_over_path(path, fun.(field, acc), fun)
  end

  def reduce_over_path([field], acc, fun) do
    fun.(field, acc)
  end

  def reduce_over_path(fields = [_|_], acc, fun) do
    Enum.map(fields, fn
      field ->
        reduce_over_path(field, acc, fun)
    end)
  end

  def reduce_over_path({field, rest}, acc, fun) do
    reduce_over_path(rest, fun.(field, acc), fun)
  end

  def reduce_over_path(field, acc, fun) do
    fun.(field, acc)
  end
end

Path.reduce_over_path([:a, b: [:c, d: :e]], [], fn x, acc -> acc ++ [x] end)
# Returns this:
[
  [:a],
  [ [:b, :c], [:b, :d, :e] ]
]

The problem is the nested array.
Do I need to use Dijkstra’s Shortest Path Algorithm or something?

2

Is just a list of atoms… “Keyword lists” are lists with binary tuples, first element beeing an atom, second element beeing an arbitrary value.

Also I’m not sure about the difference between your second and third example.

1 Like
3

Yes I know what a keyword list is, but I’m trying to get across that it should work with just a list of atoms also.

The difference between the second and third is in the input. The output is the same, but:

[:a, b: [:c, d: :e]]

[:a, b: [:c, d: [:e]]]
                ^
# There is an extra list bracket on the :e
4

You haven’t explained the algorithm you’re after. I see no clear correlation between input and output. What’s the goal?

2 Likes
5

Okay, I thought the examples would be enough sorry. Think of the list as describing a tree:

[:a, b: :c]

The one above has two paths in it, [:a] and [:b, :c]. Those paths can go deeper like so:

[:a, b: [c: [d: :e]]]

In this case we still have two possible paths: [:a] and [:b, :c, :d, :e]. We can also do this:

[:a, b: [:c, d: :e]]

In this case there are three paths: [:a] [:b, :c] and [:b, :d, :e] This one is a tree like so:

 a,    b 
      / \
    c    d
            \
             e

I essentially want to be able to reduce over the list [:a, b: [:c, d: :e]] and visit path once. In this example I would want to visit the nodes in this order: [:a, b, c, b, d, e]

6

So you want to traverse the leaves of a tree only? Not the branches? In the example you gave there’s another path and that’s [:b, :d]. But if you only want to visit the leaves and not branches then yes, I can see what you want solved.

Not sure you should go with lists though. Is what you are after a binary tree?

If so, use tuples. This oldish article could help you as well: http://learningelixir.joekain.com/tree-ops/

EDIT: Here’s some code, pretty dirty and tested on 2 inputs only:

defmodule Btree do
  def visit([{_parent, child} | rest], callback) do
    visit(child, callback)
    visit(rest, callback)
  end

  def visit([leaf | rest], callback) do
    visit(leaf, callback)
    visit(rest, callback)
  end

  def visit([], _callback), do: :ok

  def visit(v, callback), do: callback.(v)

  def test1() do
    visit([:a, b: [:c, d: :e]], &IO.inspect/1)
    IO.puts "---"
    visit([a: :b, c: :d, e: [f: :g]], &IO.inspect/1)
  end
end

This will print only the leaves of both trees.

Again though, I recommend a cleaner approach to binary trees.

7

Thanks!

another path and that’s [:b, :d] .

good point! I don’t care about that. I suppose I care about all paths to the end.

Is what you are after a binary tree?

The problem is I don’t have a choice for the public API. I want to try and use the same API that is used for

Repo.preload([model: [:another_relation]])

as the change I am making is to try and allow Ecto.Changeset.validate_thing function to take a path to the thing they are trying to validate.

Thanks though I think I can rethink the approach a little.

8

Sure, I understand. Another alternative approach you might go for is to make a proper binary tree like in the linked post and then have custom functions that store it in this form that you need.

9

By way of update, I solved the problem and turned it into a library :tada: