fugafuga.write

日々のログ

すごいH本 part99

Zipper

Haskellで木構造の要素を変更したい場合、ルート要素から指定の要素が見つかるまで探索が必要になる。 また、前回更新した要素の近くの要素を更新したい場合などでもルートから探す必要がある。 これは効率が悪い。

そこでZipperを使ってデータ構造の要素の更新を簡単にする。

続きを読む

すごいH本 part98

モナドを作る

モナドは作りたいと思って作るものではない。 ある問題の側面をモデル化した型を作り、 後からその型が文脈付きの値を表現していてモナドのように振る舞うとわかった場合に、 Monadインスタンスを与える場合が多い。

リスト [3,5,9] を、整数3, 5, 9が同時に存在している状態だとすると、 それぞれの数の存在確率の情報が足りないと気づく。

確率も含めて表現するとこう、

[(3,0.5),(5,0.25),(9,0.25)]

数学では確率は0から1までの実数で表現する。 確率を浮動小数で表現した場合、すぐに精度が落ちて困る。 そのため、Haskellには分数のためのデータ型がある。 Rationalと呼ばれる、Data.Ratioモジュールにある。 分子と分母は%記号で区切る。

*Main Data.Ratio> 1%4
1 % 4
*Main Data.Ratio> 1%2 + 1%2
1 % 1
*Main Data.Ratio> 1%3 + 5%4
19 % 12

確率をRationalで表す。

*Main Data.Ratio> [(3,1%2),(5,1%4),(9,1%4)]
[(3,1 % 2),(5,1 % 4),(9,1 % 4)]

これを newtype で新しい型に包む

import Data.Ratio

newtype Prob a = Prob { getProb :: [(a, Rational)] } deriving Show

リストはファンクターであるので、Probもファンクターになれる。

instance Functor Prob where
    fmap f (Prob xs) = Prob $ map (\(x, p) -> (f x, p)) xs

動作させてみる

*Main Data.Ratio> fmap negate (Prob [(-3,1 % 2),(-5,1 % 4),(-9,1 % 4)])
Prob {getProb = [(3,1 % 2),(5,1 % 4),(9,1 % 4)]}

確率の総和は常に1である。

これはモナドかどうか考える。 まず、return について。リストのreturnは値を取って単一要素のリストに入れる関数。 Probの場合も、単一要素を作るっぽい。確率は、1。 >>=は、m >>= fjoin (fmap f m) が等価であることを使って確率リストを平らにすることを考える。

'a','b'が起こる確率が25%,'c','d'が起こる確率が75%とした場合の状況を確率リストで表す。

thisSituation :: Prob (Prob Char)
thisSituation = Prob
    [(Prob [('a',1%2),('b', 1%2)], 1%4)
    ,(Prob [('c',1%2),('d', 1%2)], 3%4)
    ]

型が Prob (Prob Char)と入れ子になっている。これを平らにする。

flatten :: Prob (Prob a) -> Prob a
flatten (Prob xs) = Prob $ concat $ map multAll xs
    where multAll (Prob innerxs, p) = map (\(x, r) -> (x, p*r)) innerxs

関数 multAll は、確率リストとある確率pのタプルをとって、 リストの中の確率をp倍して、事象と確率の組のリストを返す関数。

flatten は、multAll を入れ子確率リストの各要素を適用してまわり、 得られた入れ子リストを最後にリストとして平らにする。

Monadインスタンスを書く。(Applicativeも書かないとGHCがエラー出す)

参考 : https://qiita.com/Aruneko/items/e72f7c6ee49159751cba

instance Applicative Prob where
    pure x = Prob [(x,1%1)]

instance Monad Prob where
    return x = Prob [(x,1%1)]
    m >>= f = flatten (fmap f m)
    fail _ = Prob []

モナドインスタンスが手に入ったので、 確率計算をするプログラムを書く。 普通のコインが2枚と、10回投げると9回裏がでるよう細工されたコイン1枚を全部同時に投げて、 全部裏が出る確率をもとめる。

data Coin = Heads | Tails deriving (Show, Eq)

coin :: Prob Coin
coin = Prob [(Heads,1%2),(Tails,1%2)]

loadedCoin :: Prob Coin
loadedCoin = Prob [(Heads,1%10),(Tails,9%10)]

flipThree :: Prob Bool
flipThree = do
    a <- coin
    b <- coin
    c <- loadedCoin
    return (all (==Tails) [a,b,c])

実行

*Main Data.Ratio> getProb flipThree
[(False,1 % 40),(False,9 % 40),(False,1 % 40),(False,9 % 40),(False,1 % 40),(False,9 % 40),(False,1 % 40),(True,9 % 40)]

3枚とも裏が出る確率は、9/40になる。

所感

自分で書ける気がしない。

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

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

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

すごいH本 part97

安全な逆ポーランド記法電卓をつくる

前に作ったRPN電卓にエラー機能をつける。

import           Control.Monad

solveRPN :: String -> Maybe Double
solveRPN st = do
    [result] <- foldM foldingFunction [] $ words st
    return result

foldingFunction :: [Double] -> String -> Maybe [Double]
foldingFunction (x:y:ys) "*"    = return ((y * x):ys)
foldingFunction (x:y:ys) "+"    = return ((y + x):ys)
foldingFunction (x:y:ys) "-"    = return ((y - x):ys)
foldingFunction xs numberString = liftM (:xs) (readMaybe numberString)

readMaybe :: (Read a) => String -> Maybe a
readMaybe st = case reads st of [(x, "")] -> Just x
                                _         -> Nothing

実行

*Main> solveRPN "1 2 * 4 +"
Just 6.0
*Main> solveRPN "1 2 * 4 + 5 *"
Just 30.0
*Main> solveRPN "1 2 * 4"
Nothing
*Main> solveRPN "1 8 werasdfasdefih"
Nothing

モナディック関数の合成

第13章で <=< は関数合成によく似ているけど普通の関数 a -> b ではなく、 a -> m b のようなモナディック関数に作用するということが書かれていた。

*Main> let f = (+1) . (*100)
*Main> f 4
401
*Main> let g = (\x -> return (x+1)) <=< (\x -> return (x*100))
*Main> Just 4 >>= g
Just 401

複数の関数をリストに持っているとき、 全部合成して1つの関数を作る場合は id をアキュムレータ、. を2引数関数として畳み込むとよい。

*Main> let f = foldr (.) id [(+8),(*100),(+1)]
*Main> f 1
208

モナディック関数も同じように合成できる。 . の代わりに <=<id の代わりに return を使うとよい。

前にチェスのナイトを3手以内で移動できるかどうか判定するプログラムを改良する。

import           Control.Monad

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')

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

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

モナディックに合成して、より一般化する

import           Control.Monad
import           Data.List

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')

inMany :: Int -> KnightPos -> [KnightPos]
inMany x start = return start >>= foldr (<=<) return (replicate x moveKnight)

canReachIn :: Int -> KnightPos -> KnightPos -> Bool
canReachIn x start end = end `elem` inMany x start

moveKnight を replicate して指定した数だけ実行できるようにしている。

実行

*Main> canReachIn 5 (0,0) (8,3)
True

所感

文脈もたせたまま処理できる術がちゃんと用意されている。使えるようになるまでは時間かかりそうである。

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

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

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

すごいH本 part96

便利なモナディック関数

モナドを扱う関数はモナディック関数と呼ばれる。

liftM

関数とモナド値をとって、関数でモナド値を写してくれる。 fmapっぽい。

liftM :: Monad m => (a1 -> r) -> m a1 -> m r

fmap の型

fmap :: Functor f => (a -> b) -> f a -> f b

ファンクター則とモナド則を満たしている場合、fmap と liftM はまったく同じものになる。

liftM を試す

*Main> liftM (*3) (Just 8)
Just 24
*Main> fmap (*3) (Just 8)
Just 24
*Main> runWriter $ liftM not $ writer (True, "chickpeas")
(False,"chickpeas")
*Main> runWriter $ fmap not $ writer (True, "chickpeas")
(False,"chickpeas")
*Main> runState (liftM (+100) pop) [1,2,3,4]
(101,[2,3,4])
*Main> runState (fmap (+100) pop) [1,2,3,4]
(101,[2,3,4])

fmap と liftM は同じ動きしてる。

次はアプリカティブ値

*Main> (+) <$> Just 3 <*> Just 5
Just 8
*Main> (+) <$> Just 3 <*> Nothing
Nothing

<$>はただのfmap。<*>はこう

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

fmap に似ているが、関数自身も文脈の中に入っている。

ap という関数があり、本質的には<*>と同じだが、Applicativeの代わりにMonad型クラス制約がついている。

ap :: (Monad m) => m (a -> b) -> m a -> m b
ap mf m = do
    f <- mf
    x <- m
    return (f x)

mf は結果が関数であるようなモナド値。

使ってみる

*Main> Just (+3) <*> Just 4
Just 7
*Main> Just (+3) `ap` Just 4
Just 7
*Main> [(+1),(+2),(+3)] <*> [10,11]
[11,12,12,13,13,14]
*Main> [(+1),(+2),(+3)] `ap` [10,11]
[11,12,12,13,13,14]

モナドの威力は少なくともアプリカティブやファンクター以上である。 すべてのモナドはファンクターでもアプリカティブでもあるのにそのインスタンスになっているとは限らない。 また、ファンクターやアプリカティブファンクターが使う関数と等価なモナド版の関数が存在する。

join

任意の入れ子になったモナドは平らにできる。 このために join がある。

join :: (Monad m) => m (m a) -> m a

使ってみる

*Main> join (Just (Just 9))
Just 9
*Main> join (Just Nothing)
Nothing
*Main> join Nothing
Nothing
*Main> join [[1,2,3],[4,5,6]]
[1,2,3,4,5,6]
*Main> runWriter $ join (writer (writer (1, "aaa"), "bbb"))
(1,"bbbaaa")
*Main> join (Right (Right 9))
Right 9
*Main> join (Right (Left "error"))
Left "error"
*Main> join (Left "error")
Left "error"
*Main> runState (join (state $ \s -> (push 10, 1:2:s))) [0,0,0]
((),[10,1,2,0,0,0])

filterM

filter関数は、Haskellプログラミングの米らしい。 map は塩らしい。

filterは述語とフィルタ対象のリストを取り、述語を満たす要素だけを残してくれる。

filter :: (a -> Bool) -> [a] -> [a]

文脈を持った値を filterしたい場合、filterMを使う。Control.Monad モジュールに定義されている。

filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]

リストを取って、4より小さい要素だけを残す関数。

*Main> filter (\x -> x < 4) [9,1,5,2,10,3]
[1,2,3]

True か False だけを返すのではなく、何をしたかのログを残すような述語を作る。

import           Control.Monad.Writer.Lazy

keepSmall :: Int -> Writer [String] Bool
keepSmall x
    | x < 4 = do
        tell ["Keeping " ++ show x]
        return True
    | otherwise = do
        tell [show x ++ " is too large, throwning it away"]
        return False

実行

*Main> fst $ runWriter $ filterM keepSmall [9,1,5,2,10,3]
[1,2,3]

ログを表示してみる

*Main> mapM_ putStrLn $ snd $ runWriter $ filterM keepSmall [9,1,5,2,10,3]
9 is too large, throwning it away
Keeping 1
5 is too large, throwning it away
Keeping 2
10 is too large, throwning it away
Keeping 3

filterM を使って冪集合を作る

powerset :: [a] -> [a]
powerset xs = filterM (\x -> [True, False]) xs

実行

*Main> powerset [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

foldM

foldl のモナド版が foldM

foldl の型

foldl :: (a -> b -> a) -> a -> [b] -> a

foldM の型

foldM :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a

foldl 使ってみる

*Main> foldl (\acc x -> acc + x) 0 [2,8,3,1]
14

整数のリストを加算したいが、リストのいずれかの要素が9より大きい場合、 計算全体を失敗させたい。Maybeアキュムレータを返すようにする。

import           Control.Monad

binSmalls :: Int -> Int -> Maybe Int
binSmalls acc x
    | x > 9 = Nothing
    | otherwise = Just (acc + x)

実行

*Main> foldM binSmalls 0 [2,8,3,1]
Just 14
*Main> foldM binSmalls 0 [2,11,3,1]
Nothing

リストに9より大きい数が入っている場合、Nothingになっている。

所感

モナディック関数。中2っぽくてよい。

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

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

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