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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
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
  alias BinTree, as: BT
  alias __MODULE__, as: Z
  
  defstruct value: nil, left: nil, right: nil, trail: []
  @opaque t :: %__MODULE__{value: any,
                           left: BinTree.t | nil,
                           right: BinTree.t | nil,
                           trail: trail_t}
  @opaque trail_t :: [{:left, any, BinTree.t} | {:right, any, BinTree.t}]

  @doc """
  Get a zipper focussed on the root node.
  """
  @spec from_tree(BT.t) :: Z.t
  def from_tree(bt) do
    %__MODULE__{value: bt.value,
                left:  bt.left,
                right: bt.right}
  end

  @doc """
  Get the complete tree from a zipper.
  """
  @spec to_tree(Z.t) :: BT.t
  def to_tree(%__MODULE__{trail: [_|_]} = z), do: z |> up |> to_tree
  def to_tree(%__MODULE__{trail: []} = z) do
    %BT{value: z.value,
        left:  z.left,
        right: z.right}
  end

  @doc """
  Get the value of the focus node.
  """
  @spec value(Z.t) :: any
  def value(z) do
    z.value
  end

  @doc """
  Get the left child of the focus node, if any.
  """
  @spec left(Z.t) :: Z.t | nil
  def left(%__MODULE__{left: nil}), do: nil
  def left(z) do
    next = z.left
    %__MODULE__{value: next.value,
                left:  next.left,
                right: next.right,
                trail: [{:left, z.value, z.right}|z.trail]}
  end

  @doc """
  Get the right child of the focus node, if any.
  """
  @spec right(Z.t) :: Z.t | nil
  def right(%__MODULE__{right: nil}), do: nil
  def right(z) do
    next = z.right
    %__MODULE__{value: next.value,
                left:  next.left,
                right: next.right,
                trail: [{:right, z.value, z.left}|z.trail]}
  end

  @doc """
  Get the parent of the focus node, if any.
  """
  @spec up(Z.t) :: Z.t
  def up(%__MODULE__{trail: []} = z), do: z
  def up(%__MODULE__{trail: [{:left, val, right}|trail]} = z) do
    %__MODULE__{value: val,
                left:  %BT{value: z.value,
                           left:  z.left,
                           right: z.right},
                right: right,
                trail: trail}
  end
  def up(%__MODULE__{trail: [{:right, val, left}|trail]} = z) do
    %__MODULE__{value: val,
                left:  left,
                right: %BT{value: z.value,
                           left:  z.left,
                           right: z.right},
                trail: trail}
  end

  @doc """
  Set the value of the focus node.
  """
  @spec set_value(Z.t, any) :: Z.t
  def set_value(z, v) do
    %{z | value: v}
  end

  @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
    %{z | left: l}
  end

  @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
    %{z | right: r}
  end
end

Comments

I think it would be better to implement up/1 in terms of to_tree/1 instead of the way I did, but I'll leave that for a later iteration.

NobbZ commented 11 February 2016 at 15:32 UTC

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