List モナドは長さの変化するリストの演算を連鎖させて行うときに使います。
例としてフィボナッチ数を求めてみます。
フィボナッチ数 1つがいの兎は、産まれて2か月後から毎月1つがいずつの兎を産む。 1つがいの兎は1年の間に何つがいの兎になるか？
つがいの兎を Int 型の数字で表現します。その数字は生まれてからの月数だと思ってください。
-- 1ヶ月後のつがいの兎 -- 引数はつがいの兎で出力は1ヶ月後のつがいの兎です。 -- 産まれて2か月未満なら年齢を加算しますがつがいの兎の数は変化しません。 -- それ以上なら年齢を加算したうえに新しい0歳のつがいの兎が増えます。 nextRabbits :: Int -> [Int] nextRabbits r | r < 1 = [r+1] | otherwise = [r+1,0]
- 兎小屋をリストで表現します。兎小屋にいる各兎に1ヶ月後の状態を適用します。
- 各兎は長さ1または2のリストを返しますので、それを連結してひとつのリストにします。
{- リストモナドのインスタンス。m >>= k は concat (map k m) の演算。 リストの各要素にkを適用させて、そのリストを連結する。ひとつのリストの連結することで 次も同様に演算が出来る。 instance Monad [] where m >>= k = concat (map k m) return x = [x] fail s = [] -} > (concat.map nextRabbits) [0] -- > [1] > (concat.map nextRabbits)$(concat.map nextRabbits) [0] -- > [2,0] > (concat.map nextRabbits)$(concat.map nextRabbits)$(concat.map nextRabbits) [0] -- > [3,0,1]
- (>>=)を使うと連結を簡潔に記述できます。
> nextRabbits =<< [0] -- > [1] > nextRabbits =<< nextRabbits =<< [0] -- > [2,0] > nextRabbits =<< nextRabbits =<< nextRabbits =<< [0] -- > [3,0,1] > take 12 $ map length $ iterate (nextRabbits =<<) [0] -- > [1,1,2,3,5,8,13,21,34,55,89,144] -- これがフィボナッチ数列ですね。 > take 12 $ map length $ iterate (concat.map nextRabbits) [0] -- > [1,1,2,3,5,8,13,21,34,55,89,144]
