ElixirでCompositeパタン風な構造を扱う時の覚書

en.wikipedia.org

Compositeパタンは、再起的な構造を表現するときにしばしば顔を出すパタンで、node と leaf に同じイタンフェースを与えることで、それらを同一視して再起的に扱えるようにするしくみです。

Elixir は型付けが動的なので、特別な工夫をしなくても再起的な構造を作れますが、同一視して扱えるようにするには少し工夫必要です。

例えば。 一つの値をもつ leaf と、leaf もしくは node を二つ持つ node からtree を構築し、traverse ですべての値を渡り歩きたいばあい。

leaf1 = Tree.new_leaf(1)
leaf2 = Tree.new_leaf(2)
leaf3 = Tree.new_leaf(3)
leaf4 = Tree.new_leaf(4)
leaf5 = Tree.new_leaf(5)
leaf6 = Tree.new_leaf(6)

tree =
  Tree.new_node(
    Tree.new_node(
      Tree.new_node(leaf1, leaf2),
      leaf3
    ),
    Tree.new_node(
      leaf4,
      Tree.new_node(leaf5, leaf6)
    )
  )

Tree.Component.traverse(tree, fn a -> IO.inspect(a) end)

$ mix run sample.exs 
1
2
3
4
5
6

このとき Node が持つ二つの要素が Leaf なのか Node なのかを区別せずに関数を適用したいわけですが、その関数が Leaf や Node をパタンマッチで識別するようでは実装が硬直してしまいます。

このようなばあい、traverse/2 をプロトコルで定義し、それぞれの構造体で定義することで実現します。

具体的には、次のような実装が考えられます。

defmodule Tree do
  alias Tree.{Leaf, Node}

  def new_leaf(value) do
    Leaf.new(value)
  end

  def new_node(left, right) do
    Node.new(left, right)
  end
end

defprotocol Tree.Component do
  def traverse(component, fun)
end

defmodule Tree.Leaf do
  defstruct [:value]

  def new(value) do
    %__MODULE__{value: value}
  end

  defimpl Tree.Component do
    def traverse(%Tree.Leaf{value: value}, fun) do
      fun.(value)
    end
  end
end

defmodule Tree.Node do
  defstruct [:left, :right]

  def new(left, right) do
    %__MODULE__{left: left, right: right}
  end

  defimpl Tree.Component do
    def traverse(%Tree.Node{left: left, right: right}, fun) do
      Tree.Component.traverse(left, fun)
      Tree.Component.traverse(right, fun)
    end
  end
end

ここで問題になるのが、プロトコルを実装していない値が含まれてしまったばあいです。

Node 向けの traverse/2 の実装は、left も right も traverse/2 を定義したプロトコルを実装した構造体の値であることを前提にしています。 ですが、Elixir は型付けが動的なゆえに、このままでは任意の値を格納した Node の値を作れてしまいます。

そこで Tree.new_node/2 で Node の値を作るときに、引数に渡せる値を制限することにします。

まず、ガードの is_struct/1 を使うことで、引数に与えることができる値を構造体の値に制限します。

is_struct/2 を使えば、構造体の種類も限定できますが、今回は Leaf の値も Node の値も受け付けたいので都合がよくありません。 is_struct(left, Tree.Leaf) or is_struct(left, Tree.Node) と書けなくはないですが、プロトコルを利用するときの利点であったコードの柔軟性が失われてしまいます。

プロトコルの実装状況をガードで検証したいところですが、残念ながらそのようなガードは用意されていないようです。 ただ、関数は用意されているのでこれを利用することにします。

• Protocol.assert_impl!/2

Protocol.assert_impl!/2 は、第 1 引数にプロトコルを、第 2 引数に構造体の型になるモジュールを取ります。 また Elixir の構造体の値は、__struct__ を参照することでその値の方になるモジュールがわかるようになっています。

leaf = Tree.new_leaf(123)
#=> %Tree.Leaf{value: 123}

leaf.__struct__
#=> Tree.Leaf

node = Tree.new_node(Tree.new_leaf(123), Tree.new_leaf(456))
#=> %Tree.Node{left: %Tree.Leaf{value: 123}, right: %Tree.Leaf{value: 456}}

node.__struct__
#=> Tree.Node

これらを組み合わせてプロトコルを実装した型で引数を制限することにします。 ここでは Tree.new_node/2 の引数を検証することで、期待しない値が tree に組み込まれるのを防ぐことにします。

これで少なくとも traverse/2 を適用する時点でなく、値を構築する時点で異常を検出できるようになりました。

defmodule Tree do
  alias Tree.{Leaf, Node}

  def new_leaf(value) do
    Leaf.new(value)
  end

  def new_node(left, right) when is_struct(left) and is_struct(right) do
    Protocol.assert_impl!(Tree.Component, left.__struct__)
    Protocol.assert_impl!(Tree.Component, right.__struct__)

    Node.new(left, right)
  end
end

なお、補足として。 Tree.Node の内部構造や Tree.Node.new/2 はあくまで非公開というのが前提になります。