>>= を考える

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)

今まで、a と b が同じモナドしか理解できませんでしたが、これで a と b が異なるモナドも理解できた気がします。