zipper.exs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
defmodule BinTree do
  @moduledoc """
  A node in a binary tree.

  `value` is the value of a node.
  `left` is the left subtree (nil if no subtree).
  `right` is the right subtree (nil if no subtree).
  """
  @type t :: %BinTree{ value: any, left: BinTree.t | nil, right: BinTree.t | nil }
  defstruct value: nil, left: nil, right: nil
end

defmodule Zipper do
  @type t :: %Zipper{ focus: BinTree.t, history: List.t }
  defstruct focus: nil, history: []
  @doc """
  Get a zipper focused on the root node.
  """

  alias Zipper, as: Z

  @spec from_tree(BT.t) :: Z.t
  def from_tree(bt) do
    %Z{ focus: bt }
  end

  @doc """
  Get the complete tree from a zipper.
  """
  @spec to_tree(Z.t) :: BT.t
  def to_tree(%Z{ focus: bt, history: [] }), do: bt
  def to_tree(z) do
    z |> up |> to_tree
  end

  @doc """
  Get the value of the focus node.
  """
  @spec value(Z.t) :: any
  def value(%Z{ focus: %{ value: v }}), do: v
  def value(_), do: nil

  @doc """
  Get the left child of the focus node, if any.
  """
  @spec left(Z.t) :: Z.t | nil
  def left(z), do: get(z, :left)

  @doc """
  Get the right child of the focus node, if any.
  """
  @spec right(Z.t) :: Z.t | nil
  def right(z), do: get(z, :right)

  @doc """
  Get the parent of the focus node, if any.
  """
  @spec up(Z.t) :: Z.t
  def up(%Z{ focus: bt, history: [{direction, h}|hs] }) do
    %Z{ history: hs, focus: Map.put(h, direction, bt) }
  end

  @doc """
  Set the value of the focus node.
  """
  @spec set_value(Z.t, any) :: Z.t
  def set_value(z, v), do: put(z, v, :value)

  @doc """
  Replace the left child tree of the focus node.
  """
  @spec set_left(Z.t, BT.t) :: Z.t
  def set_left(z, l), do: put(z, l, :left)

  @doc """
  Replace the right child tree of the focus node.
  """
  @spec set_right(Z.t, BT.t) :: Z.t
  def set_right(z, r), do: put(z, r, :right)

  defp put(%Z{ focus: bt } = z, value, position) do
    %{ z | focus: Map.put(bt, position, value) }
  end

  defp get(%Z{ focus: bt, history: h }, direction) do
    case Map.pop(bt, direction) do
      { nil, _ } -> nil
      { v, new } -> %Z{ focus: v, history: [{ direction, new } | h ] }
    end
  end
end

@petertseng thinks this looks great

Comments

Thanks for your comments @petertseng! Here's an implementation that uses Map.pop to avoid the duplication of data where possible. One consequence of this is that the resultant BT structs no longer have their complete set of keys, so I had to change the inspect implementation in the test suite:

1
2
3
4
5
6
    def inspect(%BinTree{value: v} = bt, opts) do
      concat ["(", to_doc(v, opts),
              ":", (if l = Map.get(bt, :left), do: to_doc(l, opts), else: ""),
              ":", (if r = Map.get(bt, :right), do: to_doc(r, opts), else: ""),
              ")"]
    end

It's a bit surprising to me that a struct defined with default values would raise a KeyError even if the key is popped out.

zvkemp commented 11 October 2015 at 17:51 UTC

Interesting point about the default values. I guess the defaults are only provided at creation time? I will need to read a bit more before able to answer that question.

I suppose if you wanted to make this work without modifying the tests then maybe Map.put(new, direction, nil) might have been an option, but I don't find that really necessary.

petertseng commented 11 October 2015 at 18:43 UTC

Yeah, I played with put too, but I like that the read and update can be done with the single operation of pop.

zvkemp commented 11 October 2015 at 19:00 UTC

You're not logged in right now. Please login via GitHub to comment