Monadic Programming in Scheme の Haskell の例ですが、肝心の make_node のコードがないので、さっぱり理解できませんでした。試行錯誤の結果、以下のようにすると動きました。
type Numbered a = (Int, a) newtype NumberedM a = NumberedM (Int -> Numbered a) instance Monad NumberedM where NumberedM m >>= f = NumberedM $ \n -> let (n1, v) = (m n) NumberedM m' = f v (n1', v') = (m' n1) in (n1', v') return x = NumberedM $ \n -> (n, x) ---------------------------------------------------------------- incr :: NumberedM Int incr = NumberedM $ \n -> (n+1, n) ---------------------------------------------------------------- data Tree a = Nd a (Forest a) deriving Show type Forest a = [Tree a] type Value = Numbered Int ---------------------------------------------------------------- make_node :: Int -> Forest Value -> NumberedM (Tree Value) make_node val kids = incr >>= (\counter -> return (Nd (counter, val) kids)) ---------------------------------------------------------------- make_btree :: Int -> NumberedM (Tree Value) make_btree 0 = make_node 0 [] make_btree depth = do left <- make_btree (depth -1); right <- make_btree (depth -1); make_node depth [left, right] ---------------------------------------------------------------- run :: NumberedM (Tree Value) -> Int -> Tree Value run (NumberedM m) init_count = case m init_count of (_, tree) -> tree
こんな風に動きます。
run (make_btree 3) 100 → Nd (114,3) [Nd (106,2) [Nd (102,1) [Nd (100,0) [],Nd (101,0) []],Nd (105,1) [Nd (103,0) [],Nd (104,0) []]],Nd (113,2) [Nd (109,1) [Nd (107,0) [],Nd (108,0) []],Nd (112,1) [Nd (110,0) [],Nd (111,0) []]]]
make_node を実装して、ようやく >>= の型が理解できました。
(>>=) :: m a -> (a -> m b) -> m b
これは、"m" というラベルが同じであれば、中に格納される型が違っても、>>= という糊でくっ付けられるという意味なんですね。
もう一度 make_node を見てみましょう。
make_node :: Int -> Forest Value -> NumberedM (Tree Value) make_node val kids = incr >>= (\counter -> return (Nd (counter, val) kids))
inc はこうでした。
incr :: NumberedM Int incr = NumberedM $ \n -> (n+1, n)
右側の関数の型はこうです。
Int -> NumberedM (Tree Value)
この 2 つを >>= で合成すると、こうなります。
NumberedM (Tree Value)