fugafuga.write

日々のログ

すごいH本 part92

プログラムにログを追加する

ユークリッド互除法。2つの数を取り、最大公約数を求めるアルゴリズム。

gcd関数を自前で作る

gcd' :: Int -> Int -> Int
gcd' a b
    | b == 0    = a
    | otherwise = gcd' b (a `mod` b)

実行

*Main> gcd' 8 3
1

8 と 3 の最大公約数は 1 なので正解

ログの機能をつける

gcd' :: Int -> Int -> Writer [String] Int
gcd' a b
    | b == 0    = do
        tell ["Finished with " ++ show a]
    | otherwise = do
        tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]
        gcd' b (a `mod` b)

実行

*Main> fst $ runWriter (gcd' 8 3)
1
*Main> mapM_ putStrLn $ snd $ runWriter (gcd' 8 3)
8 mod 3 = 2
3 mod 2 = 1
2 mod 1 = 0
Finished with 1

非効率なリスト構築

リストはmappendの実装に ++ を使っているが、 これを使ってリストの最後にものを追加する操作はリストが長いと遅くなる。

gcdReverse :: Int -> Int -> Writer [String] Int
gcdReverse a b
    | b == 0 = do
        tell ["Finished with " ++ show a]
        return a
    | otherwise = do
        result <- gcdReverse b (a `mod` b)
        tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]
        return result

実行

*Main> mapM_ putStrLn $ snd $ runWriter (gcdReverse 8 3)
Finished with 1
2 mod 1 = 0
3 mod 2 = 1
8 mod 3 = 2

この関数は++を右結合でなく左結合で使ってしまうので非効率。 そこで、常に効率的な結合をサポートするデータ構造を使うのが一番よい。

差分リストを使う

差分リストとは実際にはリストを取って、別のリストを先頭に付け加える関数である。

[1,2,3]\xs -> [1,2,3] ++ xs は等しい。

2つの差分リストを結合する操作

f `append` g = \xs -> f (g xs)

f,gはリストを取ってその前に何かをつける関数。 f("dog"++)g("meat"++)という関数なら、次の関数と等価になる

\xs -> "dog" ++ ("meat" ++ xs)

引数に2つ目の差分リスト、そして1つ目の差分リストを適用する関数になる。 差分リストのnewtypeラッパーを作る。

newtype DiffList a = DiffList { getDiffList :: [a] -> [a] }

普通のリストと差分リストの相互変換

toDiffList :: [a] -> DiffList a
toDiffList xs = DiffList (xs++)

fromDiffList :: DiffList a -> [a]
fromDiffList (DiffList f) = f []

差分リストのMonoidインスタンス

instance Monoid (DiffList a) where
    mempty = DiffList (\xs -> [] ++ xs)
    (DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))

mempty は id 関数であり、mappend は関数合成になっている。

実行

*Main> fromDiffList (toDiffList [1,2,3,4] `mappend` toDiffList [1,2,3])
[1,2,3,4,1,2,3]

これを使って、gcdReverse の効率を上げる

gcdReverse :: Int -> Int -> Writer (DiffList String) Int
gcdReverse a b
    | b == 0 = do
        tell (toDiffList ["Finished with " ++ show a])
        return a
    | otherwise = do
        result <- gcdReverse b (a `mod` b)
        tell (toDiffList [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)])
        return result

実行

*Main> mapM_ putStrLn . fromDiffList . snd . runWriter $ gcdReverse 110 34
Finished with 2
8 mod 2 = 0
34 mod 8 = 2
110 mod 34 = 8

性能の比較

差分リストの性能比較をする

まず、差分リストから

finalCountDown :: Int -> Writer (DiffList String) ()
finalCountDown 0 = do
    tell (toDiffList ["0"])
finalCountDown x = do
    finalCountDown (x-1)
    tell (toDiffList [show x])

実行

*Main> mapM_ putStrLn . fromDiffList . snd . runWriter $ finalCountDown 500000
0
...
500000

普通のリストの場合

finalCountDown' :: Int -> Writer [String] ()
finalCountDown' 0 = do
    tell ["0"]
finalCountDown' x = do
    finalCountDown' (x-1)
    tell [show x]

実行

*Main> mapM_ putStrLn . snd . runWriter $ finalCountDown' 500000
0
...

めっちゃ遅い。

所感

実際に動かしてみることでかなり性能差があることがわかった。

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

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

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

すごいH本 part91

Writer

Writerモナドはもう1つの値がくっついた値を表し、付加された値はログのように振る舞う。 Writerモナドを使うと、一連の計算を行っている間全てのログが単一のログ値にまとめて記録されることを保証できる。

盗賊団の人数をとり、それが大きな盗賊団であるかを返す関数

isBigGang :: Int -> (Bool, String)
isBigGang x = x > 9

ただ True or False を返すだけでなく、この関数が何をしたかを示す文字列も一緒に返してほしい場合、

isBigGang :: Int -> (Bool, String)
isBigGang x = (x > 9, "Compared gang size to 9.")

タプルが返るようになり、値に文脈がついた。

*Main> isBigGang 3
(False,"Compared gang size to 9.")
*Main> isBigGang 30
(True,"Compared gang size to 9.")

(3, "Smallish gang.") を渡したい場合どうすればよいか

applyLog :: (a, String) -> (a -> (b, String)) -> (b, String)
applyLog (x, log) f = let (y, newLog) = f x in (y, log ++ newLog)

上記のような関数をつくる。(a, String)値はログを表す値が付いているという文脈を持つ。

実行

*Main> (3, "Smallish gang.") `applyLog` isBigGang
(False,"Smallish gang.Compared gang size to 9.")
*Main> (30, "A freaking platoon..") `applyLog` isBigGang
(True,"A freaking platoon..Compared gang size to 9.")

モノイドの助けを借りる

ログはStringである必要はない

applyLog :: (a, [c]) -> (a -> (b, [c])) -> (b, [c])

applyLogをByteStringに使えるかどうか。リストしか許容していないので使えない。 そこで、リストもByteStringも Monoid型クラスのインスタンスであることを利用する。

*Main B> [1,2,3] `mappend` [4,5,7]
[1,2,3,4,5,7]
*Main B> B.pack [99,104,105] `mappend` B.pack [104,117,97,104,117,97]
"chihuahua"

applyLogがMonoidを受けるようにする

applyLog :: (Monoid => m)(a, m) -> (a -> (b, m)) -> (b, m)
applyLog (x, log) f = let (y, newLog) = f x in (y, log `mappend` newLog)

実行

*Main> (3, "Smallish gang.") `applyLog` isBigGang
(False,"Smallish gang.Compared gang size to 9.")
*Main> (30, "A freaking platoon..") `applyLog` isBigGang
(True,"A freaking platoon..Compared gang size to 9.")

値とログの組という解釈は必要なくなり、値とモノイド値のおまけとして解釈できるようになった。

商品の名前と価格の組の例

import           Data.Monoid

type Food = String
type Price = Sum Int

addDrink :: Food -> (Food, Price)
addDrink "beans" = ("milk", Sum 25)
addDrink "jerky" = ("whiskey", Sum 99)
addDrink _       = ("beer", Sum 30)

Sumで包まれた値をmappendするとこうなる

*Main Data.Monoid> Sum 2 `mappend` Sum 5
Sum {getSum = 7}

食べ物と値札の組にapplyLogを使って適用する

*Main> ("beans", Sum 10) `applyLog` addDrink
("milk",Sum {getSum = 35})
*Main> ("jerky", Sum 25) `applyLog` addDrink
("whiskey",Sum {getSum = 124})
*Main> ("dogmeat", Sum 5) `applyLog` addDrink
("beer",Sum {getSum = 35})

ログだけではなく、数値の合計が計算できている。

連続で注文もできる

*Main> ("dogmeat", Sum 5) `applyLog` addDrink `applyLog` addDrink
("beer",Sum {getSum = 65})

これはモナドに似ている

Writer型

型定義

newtype Writer w a = Writer { runWriter :: (a, w) }

Monad インスタンス

instance (Monoid w) => Monad (Writer w) where
  return x = Writer (x, mempty)
  (Writer (x, v)) >>= f = let (Writer (y, v')) = f x
                            in Writer (y, v `mappend` v')

Writerをdo記法で使う

do記法は複数のWriterをまとめて何かしたいときに便利。

import           Control.Monad.Writer

logNumber :: Int -> Writer [String] Int
logNumber x = writer (x, ["Got number: " ++ show x])

multWithLog :: Writer [String] Int
multWithLog = do
    a <- logNumber 3
    b <- logNumber 5
    return (a * b)

実行

*Main> runWriter multWithLog
(15,["Got number: 3","Got number: 5"])

モノイド値だけを追記したい場合、Monad.Writer型クラスのtellが便利。 引数をモノイド値に追記し、()を返す。

*Main> :t tell
tell :: MonadWriter w m => w -> m ()

tellを入れる

multWithLog :: Writer [String] Int
multWithLog = do
    a <- logNumber 3
    b <- logNumber 5
    tell ["Gonna multiply these two"]
    return (a * b)

実行

*Main> runWriter multWithLog
(15,["Got number: 3","Got number: 5","Gonna multiply these two"])

所感

Haskellでのログはこんな感じになるのか。 H本あとちょっとで終わると思いきや相当重い。

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

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

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