#### 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

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