fugafuga.write

日々のログ

すごいH本 part90

モナド則

ある型がMonadのインスタンスとなっていることは、その型が真にモナドであることを保証しない。 真にモナドになるために、ある型はモナド則を満たす必要がある。

左恒等性

return x >>= ff x は等価である。

  • return がある値を最小限の文脈に入れるということができているかを見る
  • モナド値と普通の値での操作結果に違いがないことを確認する

Maybeモナドの場合

Prelude> return 3 >>= (\x -> Just (x+10000))
Just 10003
Prelude> (\x -> Just (x+10000)) 3
Just 10003

リストモナドの場合

Prelude> return "WoM" >>= (\x -> [x,x,x])
["WoM","WoM","WoM"]
Prelude> (\x -> [x,x,x]) "WoM"
["WoM","WoM","WoM"]

右恒等性

m >>= return の結果は m と等価である。

Prelude> Just "move on up" >>= return
Just "move on up"
Prelude> [1,2,3,4] >>= return
[1,2,3,4]
Prelude> putStrLn "Wah!" >>= return
Wah!

左恒等性と右恒等性はどちらも、return に関する法則である。 return が最小限の文脈に値を入れているかどうかを確認することが重要。

結合法則

(m >>= f) >>= gm >>= (\x -> f x >>= g) が等価である。

*Main> m = [4]
*Main> f x = return $ x + 1
*Main> g x = return $ x * 2
*Main> (m >>= f) >>= g
[10]
*Main> m >>= (\x -> f x >>= g)
[10]

掛け算のようなものをイメージする

(m * f) * g == m * (f * g)

所感

こんな法則があるのか。と納得するしかない。

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!

  • 作者: MiranLipovaca
  • 出版社/メーカー: オーム社
  • 発売日: 2017/07/14
  • メディア: Kindle版
  • 購入: 4人 クリック: 9回
  • この商品を含むブログを見る

すごいH本 part89

騎士の旅

チェス盤の上にナイトの駒が1つだけ乗っており、ナイトを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')

ナイトの位置を表す型と、ナイトの現在位置をとって移動可能な位置を全て返す関数。

実行してみる

*Main> moveKnight (6,2)
[(8,1),(8,3),(4,1),(4,3),(7,4),(5,4)]
*Main> moveKnight (8,1)
[(6,2),(7,3)]

3手でいける位置をすべて返す関数

in3 :: KnightPos -> [KnightPos]
in3 start = do
    first <- moveKnight start
    second <- moveKnight first
    moveKnight second

実行

*Main> in3 (6,2)
[(8,1),(8,3),(4,1),(4,3),(7,4),(5,4),(5,2),(5,4),(8,1),(8,5),(6,1),(6,5),(8,1),(8,3),(4,1),(4,3),(7,4),(5,4),(8,3),(8,5),(4,3),(4,5),(7,2),(7,6),(5,2),(5,6),(5,2),(8,3),(6,3),(5,4),(5,6),(8,3),(8,7),(6,3),(6,7),(8,1),(8,3),(4,1),(4,3),(7,4),(5,4),(4,1),(4,3),(3,4),(1,4),(7,2),(7,4),(3,2),(3,4),(6,1),(6,5),(4,1),(4,5),(5,2),(5,4),(1,2),(1,4),(4,1),(4,5),(2,1),(2,5),(8,1),(8,3),(4,1),(4,3),(7,4),(5,4),(8,3),(8,5),(4,3),(4,5),(7,2),(7,6),(5,2),(5,6),(4,1),(4,3),(3,4),(1,4),(4,3),(4,5),(3,2),(3,6),(1,2),(1,6),(7,2),(3,2),(6,3),(4,3),(7,4),(7,6),(3,4),(3,6),(6,3),(6,7),(4,3),(4,7),(5,2),(1,2),(4,3),(2,3),(5,4),(5,6),(1,4),(1,6),(4,3),(4,7),(2,3),(2,7),(7,2),(7,4),(3,2),(3,4),(6,1),(6,5),(4,1),(4,5),(7,4),(7,6),(3,4),(3,6),(6,3),(6,7),(4,3),(4,7),(6,1),(6,3),(7,4),(6,5),(6,7),(7,4),(7,8),(8,1),(8,3),(4,1),(4,3),(7,4),(5,4),(8,5),(8,7),(4,5),(4,7),(7,4),(7,8),(5,4),(5,8),(5,2),(5,4),(8,1),(8,5),(6,1),(6,5),(5,4),(5,6),(8,3),(8,7),(6,3),(6,7),(5,2),(5,4),(1,2),(1,4),(4,1),(4,5),(2,1),(2,5),(5,4),(5,6),(1,4),(1,6),(4,3),(4,7),(2,3),(2,7),(8,1),(8,3),(4,1),(4,3),(7,4),(5,4),(8,5),(8,7),(4,5),(4,7),(7,4),(7,8),(5,4),(5,8),(6,1),(6,3),(2,1),(2,3),(5,4),(3,4),(6,5),(6,7),(2,5),(2,7),(5,4),(5,8),(3,4),(3,8)]

全てのパターンが列挙されてよくわからん。

2つの位置をとり、その間をちょうど3手で到達できるかどうかを調べる関数を作る

canReachIn3 :: KnightPos -> KnightPos -> Bool
canReachIn3 start end = end `elem` in3 start

実行

*Main> (6,2) `canReachIn3` (6,1)
True
*Main> (6,2) `canReachIn3` (7,3)
False

3手で到達できるルートを表示する演習問題は挫折

所感

演習問題が解けない。無能感を存分に味わった。

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!

  • 作者: MiranLipovaca
  • 出版社/メーカー: オーム社
  • 発売日: 2017/07/14
  • メディア: Kindle版
  • 購入: 4人 クリック: 9回
  • この商品を含むブログを見る

すごいH本 part88

do 記法とリスト内包表記

リスト内包表記はリストモナドの構文糖衣である。

listOfTuples :: [(Int, Char)]
listOfTuples = do
    n <- [1,2]
    ch <- ['a','b']
    return (n, ch)

*Main> [(n, ch) | n <- [1,2], ch <- ['a','b']]
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]

MonadPlus と guard 関数

リスト内包表記では、filter をかけることができた。

*Main> [x | x <- [1..50], '7' `elem` show x]
[7,17,27,37,47]

7のつく数字だけを結果として返している。

この動きを解明するためには、MonadPlus と guard 関数を知る必要がある。

MonadPlus はモノイドの性質を併せ持つモナドを表す型クラス。

class Monad m => MonadPlus m where
    mzero :: m a
    mplus :: m a -> m a -> m a

mzero は モノイドでいう mempty のこと。mplusmappend のこと。リストはモノイドなので、MonadPlus のインスタンスにできる。

instance MonadPlus [] where
    mzero = []
    mplus = (++)

リストのmzeroは失敗した非決定性計算を表現する。mplusは2つの非決定的値を1つの値に結合する。

guard 関数はこのように

guard :: (MonadPlus m) => Bool -> m ()
guard True = return ()
guard False = mzero

guard は真理値を引数にとる。引数がTrueの場合()を成功を表す最小限の文脈に入れる。引数がFalseなら失敗したモナド値を作る。

*Main> import Control.Monad
*Main Control.Monad> guard (5 > 2) :: Maybe ()
Just ()
*Main Control.Monad> guard (1 > 2) :: Maybe ()
Nothing
*Main Control.Monad> guard (5 > 2) :: [()]
[()]
*Main Control.Monad> guard (1 > 2) :: [()]
[]

リストモナドでは、guard を使って解の候補をふるい落とすことができる。

*Main Control.Monad> [1..50] >>= (\x -> guard ('7' `elem` show x) >> return x)
[7,17,27,37,47]

guard に >> をつなぐとどうなるか

*Main Control.Monad> guard (5 > 2) >> return "cool" :: [String]
["cool"]
*Main Control.Monad> guard (1 > 2) >> return "cool" :: [String]
[]

guard がやっていることは、引数がFalseなら直ちに失敗を投げる。Trueならダミーの値()が入っている成功を作る。という計算を続けてよいかの判断をやっている。

do 記法で書き直す

import           Control.Monad

sevensOnly :: [Int]
sevensOnly = do
    x <- [1..50]
    guard ('7' `elem` show x)
    return x

実行

*Main Control.Monad> sevensOnly
[7,17,27,37,47]

これと同義

*Main> [x | x <- [1..50], '7' `elem` show x]
[7,17,27,37,47]

所感

リスト内包表記はモナドのちからを使って実現されていたことが判明した。

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!

  • 作者: MiranLipovaca
  • 出版社/メーカー: オーム社
  • 発売日: 2017/07/14
  • メディア: Kindle版
  • 購入: 4人 クリック: 9回
  • この商品を含むブログを見る