fugafuga.write

日々のログ

すごいH本 part95

Eitherモナド

Maybeモナドは値に失敗するかもしれないという文脈をつけられる。 Eitherモナドも失敗の文脈を扱える。しかも、失敗に値を付加できるので失敗の説明ができたりする。

Either e a は、Right値であれば正解や計算の成功、Left値であれば失敗を表す。

*Main Lib> :t Right 4
Right 4 :: Num b => Either a b
*Main Lib> :t Left "out of cheese error"
Left "out of cheese error" :: Either [Char] b

EitherのMonadインスタンスはMaybeとよく似ている。 Control.Monad.Error モジュールで定義されている。

instance (Error e) => Monad (Either e) where
    return x = Right x
    Right x >>= f = f x
    Left err >>= f = Left err
    fail msg = Left (strMsg msg)

Left e の e は、Error型クラスのインスタンスでないといけない。 Error型クラスはエラーメッセージのように振る舞える型クラス。 Error型クラスにはエラーを文字列として受け取って、その型に変換する strMsg 関数が定義されている。

モジュールロード時に以下内容の警告が出た。

<interactive>:1:1: warning: [-Wdeprecations]
    In the use of ‘strMsg’
    (imported from Control.Monad.Error, but defined in transformers-0.5.2.0:Control.Monad.Trans.Error):
    Deprecated: "Use Control.Monad.Trans.Except instead"
strMsg :: Error a => String -> a

Control.Monad.Trans.Except を使ったほうがよさそうである。

strMsg :: Error a => String -> a

String を受け取って Error型に変換する

Eitherを使ってみる

*Main Lib> Left "boom" >>= \x -> return (x+1)
Left "boom"
*Main Lib> Left "boom " >>= \x -> Left "no way!"
Left "boom "
*Main Lib> Right 100 >>= \x -> Left "no way!"
Left "no way!"

Maybeぽい動きをしている。

Right を成功する関数に渡すパターン

*Main Lib> Right 3 >>= \x -> return (x + 100)
Right 103

成功した...

本の中では型シグネチャが無いとエラーになると書いてあった

*Main Lib> Right 3 >>= \x -> return (x + 100) :: Either String Int
Right 103

こんな感じで指定する

練習問題

以前やったピエールのバランス棒に何羽の鳥が止まっていたかわかるようにする。

import           Control.Monad.Except

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

landLeft :: Birds -> Pole -> Either String Pole
landLeft n (left, right)
    | abs (left + n - right) < 4 = Right (left + n, right)
    | otherwise = Left $ birdsCount (left, right)

landRight :: Birds -> Pole -> Either String Pole
landRight n (left, right)
    | abs (left - (right + n)) < 4 = Right (left, right + n)
    | otherwise = Left $ birdsCount (left, right)

birdsCount :: Pole -> String
birdsCount (left, right) = "Pierre fell off the rope!!" ++
                            " birds on the left: " ++ show left ++
                            ",birds on the right: " ++ show right

banana :: Pole -> Either String Pole
banana p = Left $ birdsCount p

routine :: Either String Pole
routine = do
    start <- return (0, 0)
    first <- landLeft 2 start
    second <- landRight 2 first
    third <- landLeft 1 second
    banana third

最終的にバナナで滑って落ちるようにした。

実行

*Main> routine
Left "Pierre fell off the rope!! birds on the left: 3,birds on the right: 2"

最後のバナナを取り除き、落ちないパターン

*Main> routine
Right (3,2)

所感

初めて自分の力で練習問題ができたように思う。嬉しい。

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

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

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

すごいH本 part94

計算の状態

状態を扱うためにHaskellにはStateモナドが用意されている。

状態付きの計算

状態付きの計算とは、ある状態を取って、更新された状態と一緒に計算結果を返す関数として表現できる。

s -> (a, s)

s は状態の型で、 a は状態付き計算の結果。 このような状態付きの計算も、文脈付きの値だとみなすことができる。 計算の結果が「生の値」 であり、その計算結果を得るためには初期状態を与える必要があること、 そして、計算の結果を得るのと同時に新しい状態が得られるというのが文脈にあたる。

スタックと石

stackデータ構造をモデル化する。

  • Push : スタックのてっぺんに要素を積む
  • Pop : スタックのてっぺんの要素を取り除く
type Stack = [Int]

pop :: Stack -> (Int, Stack)
pop (x:xs) = (x, xs)

push :: Int -> Stack -> ((), Stack)
push a xs = ((), a:xs)

スタックをシミュレートするコードを書く

stackManip :: Stack -> (Int, Stack)
stackManip stack = let
    ((), newStack1) = push 3 stack
    (a, newStack2) = pop newStack1
    in pop newStack2

実行

*Main> stackManip [5,8,2,1]
(5,[8,2,1])

ところが、Stateモナドを使うと次のように書けちゃう

stackManip = do
    push 3
    a <- pop
    pop

Stateモナド

Control.Monad.Stateモジュールは、状態付き計算を包んだ newtype を提供している。

newtype State s a = State { runState :: s -> (a, s) }

State s a は s 型の状態を操り、a 型の結果を返す状態付き計算。

状態付き計算のMonadインスタンス

instance Monad (State s) where
    return x = State $ \x -> (x, s)
    (State h) >>= f = State $ \s -> let (a, newState) = h s
                                        (State, g) = f a
                                    in g newState

return は値を取って常にその値を結果として返すような状態付き計算。 >>= は2つの状態付き計算を繋げられる。

先程の処理をStateモナド使って書き換える

import Control.Monad.State

pop :: State Stack Int
pop = state $ \(x:xs) -> (x, xs)

push :: Int -> State Stack ()
push a = state $ \xs -> ((), a:xs)

stackManip :: State Stack Int
stackManip = do
    push 3
    a <- pop
    pop

実行

*Main> runState stackManip [5,8,2,1]
(5,[8,2,1])

pop の結果 a は一度も使っていないのでこう書ける

stackManip :: State Stack Int
stackManip = do
    push 3
    pop
    pop

もう少し複雑なスタックの処理を書く。 スタック1つの数を取り出して、5だったら元に戻す。 5ではなかった場合、3と8を積む。

stackStuff :: State Stack ()
stackStuff = do
    a <- pop
    if a == 5
        then push 5
        else do
            push 3
            push 8

実行

*Main> runState stackStuff [9,0,1,2,0]
((),[8,3,0,1,2,0])

stackManip と stackStuff はどちらも状態付き計算なのでこの2つをつなげることができる。

moreStack :: State Stack ()
moreStack = do
    a <- stackManip
    if a == 100
        then stackStuff
        else return ()

実行

*Main> runState moreStack [100,9,3,6,22,1,0]
((),[8,3,3,6,22,1,0])

状態の取得と設定

Stateモナドを扱うための便利な型クラスMonadStateがある。 get と put という関数が使える。

get の実装

get = state $ \s -> (s, s)

put の実装

put newState = state $ \s -> ((), newState)

put と get を使う

stackeyStack :: State Stack ()
stackeyStack = do
    stackNow <- get
    if stackNow == [1,2,3]
        then put [8,3,1]
        else put [9,2,1]

get と put を使って pop と push を書き換える

pop :: State Stack Int
pop = do
    (x:xs) <- get
    put xs
    return x

push :: Int -> State Stack ()
push x = do
    xs <- get
    put (x:xs)

乱数とStateモナド

Stateモナド使って乱数を扱う処理を書く

import System.Random
import Control.Monad.State

randomSt :: (RandomGen g, Random a) => State g a
randomSt = state random

乱数ジェネレーターは状態付き計算であるので、state関数を使ってStateのnewtypeに包めば、 状態の扱いをモナドに任せることができる。

コインを3枚投げる処理はこう書けるようになる。

threeCoins :: State StdGen (Bool, Bool, Bool)
threeCoins = do
    a <- randomSt
    b <- randomSt
    c <- randomSt
    return (a, b, c)

実行

*Main> runState threeCoins (mkStdGen 33)
((True,False,True),680029187 2103410263)

所感

だいたいわからん。複雑なモナドになるとコードが何してるかわからなくなる。 とりあえず前に進むこととする。

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

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

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

すごいH本 part93

Reader

関数の型 (->) r はファンクターであり、アプリカティブファンクターであるばかりでなく、モナドでもある。 関数にとっての文脈とは、値がまだ手元になく、値がほしければその関数を別の何かに適用しないといけない。 というもの。

instance Monad ((->) r) where
    return x = \_ -> x
    h >>= f = \w -> f (h w) w

return は最小限の文脈。値を取って値を返す。引数を無視すると必ず同じ値を返す。 >>=は、モナド値を入力してモナド値を返すので、ある関数を別の関数に入力した結果として関数を返す。 この場合、f に h を適用している。

Readerモナド

関数モナドを使っている do 式

import Control.Monad.Instances

addStuff :: Int -> Int
addStuff = do
    a <- (*2)
    b <- (+10)
    return (a+b)

実行

*Main> addStuff 3
19

do式は常にモナド値を生み出すもの。この場合、do式は関数モナドを返す。 (*2)(+10)はどちらも3に適用される。return (a+b)も3に適用されるが、 引数を無視して常にa+bを返している。

関数モナドはReaderモナドと呼ばれている。全ての関数が共通の情報を読むから。

最後の引数が届くのを待っている関数がたくさんあって、 しかもそれらに渡したい値は全部同じという状況であればReaderモナドを使って未来の結果を取り出すことができる。

所感

理解が苦しくなってきた。モナドをはじめから復習する必要がある。

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

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

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

すごい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回
  • この商品を含むブログを見る