2026-09-13
TreeInsert.hs
data Tree a = Leaf | Node (Tree a) a (Tree a)
insert :: Ord a => a -> Tree a -> Tree a
-- write this: insert x into the binary search tree;
-- if x is already there, return the tree unchanged
二分探索木に値を1つ加えた新しい木を返すinsertを、パターンマッチとガードを使って実装してください。
Reference
insert :: Ord a => a -> Tree a -> Tree a
insert x Leaf = Node Leaf x Leaf
insert x t@(Node l y r)
| x < y = Node (insert x l) y r
| x > y = Node l y (insert x r)
| otherwise = t
Treeの2つの構成子にそれぞれ1つの式が対応し、データ型の定義がそのまま関数の場合分けになります。Haskellの値は書き換えられないので、「挿入」は新しい木を返すことですが、木全体をコピーするわけではありません。作り直すのは根から挿入位置までの経路上のノードだけで、たとえばx < yのときの右部分木rは、元の木と新しい木で同じものを共有します。すでに値があるときはt@で受けた元の木をそのまま返すので、何も作りません。元の木は挿入後も変わらず使えるので、変更前と変更後の両方を安心して持っていられます。これは参考実装であり、唯一の正解ではありません(ガードの代わりにcompare x yをcaseで分けても書けます)。