# 実践PBT輪読会
## 第8章 標的型プロパティ (2)
2025/05/27 [@kdnakt](https://twitter.com/kdnakt)
---
## 今回の範囲
### 第8章 標的型プロパティ
- 8.2 実践 標的型プロパティ
※8.3以降は次回
---
#### 8.2 実践 標的型プロパティ
- 二分探索木の例を考える
- 普通のプロパティ
- データがランダム
- 木の両側へデータが自然に配分
- 標的型プロパティ
- 木構造を偏らせる
----
#### 二分探索木を作る関数
```elixir!
def to_tree(list) do
Enum.reduce(list, nil, fn x, acc ->
insert(x, acc)
end)
end
def insert(n, {:node, n, l, r}), do: {:node, n, l, r}
def insert(n, {:node, m, l, r}) when n < m,
do: {:node, m, insert(n, l), r}
def insert(n, {:node, m, l, r}) when n > m,
do: {:node, m, l, insert(n, r)}
def insert(n, {:leaf, n}), do: {:leaf, n}
def insert(n, {:leaf, m}) when n < m, do: {:node, n, nil, {:leaf, m}}
def insert(n, {:leaf, m}) when n > m, do: {:node, n, {:leaf, m}, nil}
def insert(n, nil), do: {:leaf, n}
```
----
#### 二分木の平衡
```elixir!
# 左右の内部ノード数を数える
def sides({:node, _, l, r}) do
{ll, lr} = sides(l)
{rl, rr} = sides(r)
{count_inner(l) + ll + lr, count_inner(r) + rl + rr}
end
def sides(_), do: {0, 0}
def count_inner({:node, _, _, _}), do: 1
def count_inner(_), do: 0
```
----
#### 二分木のジェネレータの平衡を確認
```elixir!
property "tree regular" do
forall t <- tree() do
weight = sides(t)
IO.inspect(weight)
true
end
end
```
----
#### mixで特定行のテストを実行する
```shell!
$ mix test test/target_test.exs:35
Running ExUnit with seed: 699040, max_cases: 20
Excluding tags: [:test]
Including tags: [location: {"test/target_test.exs", 35}]
{0, 0}
（省略）
.{15, 5}
.{2, 8}
.
OK: Passed 100 test(s).
.
Finished in 0.09 seconds (0.00s async, 0.09s sync)
4 properties, 0 failures, 3 excluded
```
----
#### 偏った木をテストする
```elixir!
property "tree" do
# forallから変更
forall_targeted t <- tree() do
weight = sides(t)
{left, right} = weight
IO.inspect(weight)
# 左を大きく、右を小さく偏らせる
maximize(left - right)
true
end
end
```
- regularのテストと比べ遅い
- 焼きなまし法の計算が重い
- maximizeで探索を実行している
---
### 8.2.1 近傍関数を書く
- 焼きなまし法だけで全て実現は不可
- 効果的な近傍(※)選択が重要
- ※探索を進めるための次の変更
- `user_nf(generator, nf)`マクロ
- 近傍として独自の関数を利用可能
- `nf`：次の値を生成する関数
----
#### user_nf()マクロの使い方
```elixir!
property "example" do
forall_targeted v <- user_nf(list(integer()), next_list()) do
some_check(v)
end
end
# 近傍として利用する独自の関数。無名関数を返す
defp next_list() do
# 第１引数: 直前に生成される値
# 第２引数: 焼きなまし法の温度パラメータ
fn prev_value, {depth, current_temperature} ->
let(v <- some_generator(), do: modify(v, prev_value))
end
end
```
----
#### 木構造のプロパティにおける独自の近傍関数
```elixir!
property "tree neighbor" do
forall_targeted t <- user_nf(tree(), next_tree()) do
{left, right} = sides(t)
maximize(left - right)
true
end
end
def next_tree() do
fn old_tree, {_, t} ->
let n <- integer() do
insert(trunc(n * t * 100), old_tree)
end
end
end
```
----
#### NOTE: 温度の使い方
- 焼きなまし法で近傍選択に温度を使うべきではないという主張もある
- 温度はそもそも解を受理するかどうかを誘導するもの
- 温度が高いほど多様な解が受理される
- 早い段階でより多くの変化が必要な場合、近傍を探索する空間も温度に合わせて調整可能
---
### 8.2.2 多様性と探索
- Q. いつ近傍関数を使うべきか？
独自の近傍関数を使う影響は？
- A. 試行錯誤するほかない
- 単純な近傍関数：最初のデータの変形
- テストごとの変化は乏しい
- 効率的になる可能性もある
- できる限りデフォルトの近傍関数を使うべき
- まずはメトリクスを調整する
- それでもうまくいかないなら独自実装
----
#### 独自の探索機構
```elixir!
property "tree search" do
# not_existsイテレーションのたびに探索改善
# forallで入力値の多様性を改善
forall l <- list(integer()) do
not_exists t <- user_nf(let(x <- l, do: to_tree(x)), next_tree()) do
{left, right} = sides(t)
maximize(left - right)
false # NOT_EXISTSがパスしないように
end
end
end
```
----
#### forall + not_exists
- forallを100回、not_existsを1000回実行
- 合計10万回実行するので1-2秒かかる
- 近傍関数の実装時間・複雑性と、結果を待つ時間のトレードオフ
- デフォルトの探索：速度と品質が得られる
---
### まとめ
- 標的型プロパティで期待する結果が得られないこともある
- user_nfマクロで近傍関数を独自実装
- 独自の探索も実装できる
- 時間・品質のトレードオフ
- [今日のコード](https://github.com/kdnakt/pbt-elixir/blob/main/target/test/target_test.exs)
---
### To Be Continued...
- 8.3 独創的に考える
- 8.4 まとめ
{"title":"実践PBT輪読会 第8章 標的型プロパティ (2)","slideOptions":"{\"transition\":\"slide\"}","description":"2025/05/27 @kdnakt","contributors":"[{\"id\":\"df36d0f0-b67e-41ac-96b3-f3988326d230\",\"add\":4125,\"del\":194}]"}