Monad

monad.hs

-- モナドは強化されたアプリカティブファンクタ−。
-- アプリカティブファンクターは文脈の付いた値に, 文脈を保ったまま普通の関数を適用させてくれる。
-- ただの 1 という値を文脈を持った Just 1 にしたりする関数は pure, 文脈を持った値に関数を適用するのが <*>

<*> :: (Applicative f) => f (a -> b) -> f a -> f b

(*) <$> Just 2 <*> Just 8 -- ((*) Just 2) -> Just 8

-- モナドは普通の値 a をとって文脈付きの値を返す関数に, 文脈付きの値 m a を渡すときに用いる。

class Monad m where
  return :: a -> m a -- pure
  (>>=) :: (Monad) m => m a -> (a -> m b) -> m b -- bind
  (>>) :: m a -> m b -> m b
  x >> y = x >>= \_ -> y

-- 失敗可能性のある計算をバインドを用いて綺麗に表現できる
-- Pole に Birds を乗せていき, バランスを取れなくなったら失敗する例

type Birds = Int
type Pole = (Birds, Birds)

landLeft :: Birds -> Pole -> Maybe Pole
landLeft n (left, right)
  | abs ((left + n) - right) < 4 = Just (left + n, right)
  | otherwise                    = Nothing
landRight :: Birds -> Pole -> Maybe Pole
landRight n (left, right)
  | abs (left - (right + n)) < 4 = Just (left, right + n)
  | otherwise                    = Nothing

return (0, 0) >>= landRight 2 >>= landLeft 2 >>= landRight 2 -- 失敗可能性のある計算をバインドして綺麗に表現できる

-- 非決定性計算にも有効
-- チェス盤の上でナイトを 3 回動かして特定のマスまで移動出来るかをリストモナドを使って検証する例
-- リストモナドはリストを合成する

type KnightPos = (Int, Int)

moveKnight :: KnightPos -> [KnightPos]
moveKnight (c, r) = do
  (c', r') <- [
    (c + 2, r - 1), (c + 2, r + 1), (c - 2, r - 1), (c - 2, r + 1),
    (c + 1, r - 2), (c + 1, r + 2), (c - 1, r - 2), (c - 1, r + 2)
  ] -- ナイトの動き
  guard (c' `elem` [1..8] && r' `elem` [1..8]) -- 盤上に収まるように
  return (c', r')

step3 :: KnightPos -> [KnightPos] -- 3 ステップで動かすパターンを網羅
step3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight -- バインドして可能な手を列挙

canReach3Step :: KnightPos -> KnightPos -> Bool -- 3 ステップで指定した位置に到達出来るか
canReach3Step start end = end `elem` step3 start -- 3 ステップで到達出来る位置に end が含まれているか