stuck on list to tree parsing

58 views
Skip to first unread message

Brian Bugh

unread,
Aug 28, 2016, 2:20:12 PM8/28/16
to elixir-lang-talk
I'm incredibly stuck on something that would be very easy in imperative, but I just can't figure it out with Elixir in a properly functional way.  I want to turn this:

[:input, :loop_begin, :output, :loop_begin, :decrement, :loop_end, :input, :loop_end]

into this:

[:input, [:loop_begin, :output, [:loop_begin, :decrement, :loop_end], :input, :loop_end]]

Basically - any time there's a :loop_begin it makes a new list, and then closes the list with :loop_end

This is the closest that I've gotten, but it (obviously) stops as soon as it hits the first :loop_end

  def tree(tokens), do: do_tree(tokens, [])

  defp do_tree
([:loop_begin|rest], acc) do
   
[tree(rest, [:loop_begin]) | acc]
 
end

  defp do_tree
([:loop_end|rest], acc) do
   
[:loop_end, acc]
 
end

  defp do_tree
([t|rest], acc), do: map(rest, [t | acc])

It's like I need to consume items sometimes but not others, and I can't figure it out. Every variation I've come up with in the last couple of hours has been a flop. 

Any suggestions? This seems like something that would be obvious if I had more functional experience.

Thanks!

-Brian

José Valim

unread,
Aug 28, 2016, 2:55:26 PM8/28/16
to elixir-l...@googlegroups.com
Let's start with the regular traversal "template":

defmodule Grouper do
  def group(list) do
    group(list, [])
  end

  defp group([h | t], acc) do
    group(t, [h | acc])
  end
  defp group([], acc) do
    Enum.reverse(acc)
  end
end

The code above allow us to traverse the whole list and return it as it was.

Now we need to add a clause to group/2 that detects :loop_begin and starts the looping construct:

  defp group([:loop_begin | t], acc) do
    {current, rest} = loop(t, [:loop_begin])
    group(rest, [current | acc])
  end

The loop construct is similar to group, it receives a list and an accumulator (which starts with the value of [:loop_begin]) and will traverse the list until :loop_end is found, returning the grouped loop and the remaining data:

  defp loop([:loop_end | t], acc) do
    {Enum.reverse([:loop_end | acc]), t}
  end
  defp loop([h | t], acc) do
    loop(t, [h | acc])
  end

Notice I did not add a loop([], acc) clause. If the list terminates without a loop_end, it should fail. This allows us to handle a loop but not a loop within a loop. To do so, we would need tp add a similar loop_begin clause as we did to group:

  defp loop([:loop_begin | t], acc) do
    {current, rest} = loop(t, [:loop_begin])
    loop(rest, [current | acc])
  end

Overall we have:

defmodule Grouper do
  def group(list) do
    group(list, [])
  end

  defp group([:loop_begin | t], acc) do
    {current, rest} = loop(t, [:loop_begin])
    group(rest, [current | acc])
  end
  defp group([h | t], acc) do
    group(t, [h | acc])
  end
  defp group([], acc) do
    Enum.reverse(acc)
  end

  defp loop([:loop_begin | t], acc) do
    {current, rest} = loop(t, [:loop_begin])
    loop(rest, [current | acc])
  end
  defp loop([:loop_end | t], acc) do
    {Enum.reverse([:loop_end | acc]), t}
  end
  defp loop([h | t], acc) do
    loop(t, [h | acc])
  end
end

We could merge loop/2 and group/2 into a single function but, for such, we would need to make them return the same type (one returns a tuple, the other returns a list).

José Valim
Skype: jv.ptec
Founder and Director of R&D

--
You received this message because you are subscribed to the Google Groups "elixir-lang-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-talk+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-talk/beb86ff0-be20-462c-8996-14e251201983%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Brian Bugh

unread,
Aug 28, 2016, 4:07:05 PM8/28/16
to elixir-l...@googlegroups.com
Thanks José! Dang, I knew somewhere that I needed to keep the rest of the list when I was in a subtree, but I couldn’t get it to return properly. Thanks for explaining how you reasoned it out starting with the traversal pattern, that was very helpful. 

-Brian


You received this message because you are subscribed to a topic in the Google Groups "elixir-lang-talk" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/elixir-lang-talk/UHOIVvmUS4s/unsubscribe.
To unsubscribe from this group and all its topics, send an email to elixir-lang-ta...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-talk/CAGnRm4LmeQj2_anpG4AG%2BOTBoTThnSMZDJBHAGCWrJsNKC88aQ%40mail.gmail.com.
Reply all
Reply to author
Forward
0 new messages