id:bonotake さんに教えてもらった問題。すごく面白い。
ref: http://d.hatena.ne.jp/m-hiyama/20081022/1224640248
この問題を Haskell で言うと、
data Tree = Leaf | Node Tree Tree deriving Eq type Tree7 = (Tree, Tree, Tree, Tree, Tree, Tree, Tree)で定義される普通の二分木と、二分木の 7 つ組を考える。このとき
f :: Tree7 -> Tree g :: Tree -> Tree7の型になる 2 つの関数 f と g を定義せよ。ただし以下の 3 つの条件が満たされるものとする。
- Tree 型の任意の値 x に対して x == f (g x)
- Tree7 型の任意の値 x に対して x == g (f x)
- f と g はともに O(1)
つまり Tree と Tree7 の間の全単射を定義せよ、という問題 *1 *2 。
Tree7 というところが重要で、Tree2 〜 Tree6 だとできない (っぽい) というのがとても面白い。そしてその直感的な証明がものすごく面白い。まあこの辺の話は全部 id:bonotake さんに教えてもらったのだけど。たぶん自分では解けないしー。
で、プログラムを書いてみました。QuickCheck は通った感じです。
import Control.Monad import Test.QuickCheck data Tree = Leaf | Node Tree Tree deriving (Eq, Show) type Tree7 = (Tree, Tree, Tree, Tree, Tree, Tree, Tree) -- Tree の生成法を定義する (QuickCheck 用) instance Arbitrary Tree where arbitrary = oneof [ return Leaf, liftM2 Node arbitrary arbitrary ] -- 7 つ組の生成法を定義する (QuickCheck 用) instance (Arbitrary a, Arbitrary b, Arbitrary c, Arbitrary d, Arbitrary e, Arbitrary f, Arbitrary g) => Arbitrary (a, b, c, d, e, f, g) where arbitrary = return (,,,,,,) `ap` arbitrary `ap` arbitrary `ap` arbitrary `ap` arbitrary `ap` arbitrary `ap` arbitrary `ap` arbitrary f :: Tree7 -> Tree -- (ひみつ) g :: Tree -> Tree7 -- (ひみつ) -- QuickCheck で検査する main :: IO () main = do quickCheck $ \x -> x == f (g x) quickCheck $ \x -> x == g (f x)
$ ghc --make seven-trees.hs $ ./seven-trees OK, passed 100 tests. OK, passed 100 tests.
解答や解説は檜山さんの後で。
追記:
再帰しちゃダメという条件が抜けていたので、計算量の条件を付け足してみました。不備があったら教えてください。
